Submission #1175013
Source Code Expand
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cstdlib>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }
const ll INF = 0x3fffffff;
int H, W, K, T;
int A[500], B[500], C[500], D[500];
int cr[10005][50][50];
vector<string> move(){
vector<string> ret;
for(int i=ret.size(); i<T; i++){
string s(K, '-');
bool f = true;
rep(k,K){
auto cur = pii(B[k], A[k]);
int x = D[k];
int y = C[k];
if( i % 250 < 150 && rand() % 100 < 50 ){
x = (int)(2*x > W) * (W-1);
y = (int)(2*y > H) * (H-1);
}
cr[i+1][ cur.Y ][ cur.X ] = k;
{
//int rate = (i-200)*(i-200)/1000 + 10;
int rate = i/100 + 10;
if( i > 450 ) rate += i*i;
if( rand() % rate == 0 ) x = min(W-1, cur.X+1);
else if( rand() % rate == 0 ) x = max(0, cur.X-1);
else if( rand() % rate == 0 ) y = min(H-1, cur.Y+1);
else if( rand() % rate == 0 ) y = max(0, cur.Y-1);
}
if( x > cur.X && cr[i][ cur.Y ][ cur.X+1 ] == -1 && cr[i+1][ cur.Y ][ cur.X+1 ] == -1 ){
s[k] = 'R';
B[k]++;
cr[i+1][ cur.Y ][ cur.X ] = -1;
cr[i+1][ cur.Y ][ cur.X+1 ] = k;
f = false;
}else if( x < cur.X && cr[i][ cur.Y ][ cur.X-1 ] == -1 && cr[i+1][ cur.Y ][ cur.X-1 ] == -1 ){
s[k] = 'L';
B[k]--;
cr[i+1][ cur.Y ][ cur.X ] = -1;
cr[i+1][ cur.Y ][ cur.X-1 ] = k;
f = false;
}else if( cur.Y < y && cr[i][ cur.Y+1 ][ cur.X ] == -1 && cr[i+1][ cur.Y+1 ][ cur.X ] == -1){
s[k] = 'D';
A[k]++;
cr[i+1][ cur.Y ][ cur.X ] = -1;
cr[i+1][ cur.Y+1 ][ cur.X ] = k;
f = false;
}else if( cur.Y > y && cr[i][ cur.Y-1 ][ cur.X ] == -1 && cr[i+1][ cur.Y-1 ][ cur.X ] == -1){
s[k] = 'U';
A[k]--;
cr[i+1][ cur.Y ][ cur.X ] = -1;
cr[i+1][ cur.Y-1 ][ cur.X ] = k;
f = false;
}
}
if(f) break;
ret.push_back( s );
}
return ret;
}
int main(){
//ios_base::sync_with_stdio(0);
Fill(cr, -1);
srand(10);
cin >> H >> W >> K >> T;
rep(i,K){
cin >> A[i] >> B[i] >> C[i] >> D[i];
A[i]--;
B[i]--;
C[i]--;
D[i]--;
cr[0][ A[i] ][ B[i] ] = i;
}
auto ans = move();
cout << ans.size() << endl;
for(auto t: ans){
cout << t << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
oyas |
Language |
C++14 (GCC 5.4.1) |
Score |
29246 |
Code Size |
2916 Byte |
Status |
AC |
Exec Time |
48 ms |
Memory |
98432 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
test_11 |
test_12 |
test_13 |
test_14 |
test_15 |
test_16 |
test_17 |
test_18 |
test_19 |
test_20 |
test_21 |
test_22 |
test_23 |
test_24 |
test_25 |
test_26 |
test_27 |
test_28 |
test_29 |
test_30 |
Score / Max Score |
833 / 50000 |
1150 / 50000 |
989 / 50000 |
1089 / 50000 |
787 / 50000 |
1531 / 50000 |
1113 / 50000 |
1032 / 50000 |
1139 / 50000 |
1017 / 50000 |
1353 / 50000 |
1240 / 50000 |
1003 / 50000 |
660 / 50000 |
937 / 50000 |
1409 / 50000 |
1040 / 50000 |
1192 / 50000 |
532 / 50000 |
349 / 50000 |
996 / 50000 |
561 / 50000 |
1242 / 50000 |
397 / 50000 |
975 / 50000 |
850 / 50000 |
925 / 50000 |
297 / 50000 |
1466 / 50000 |
1142 / 50000 |
Status |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
test_11 |
subtask_01_11.txt |
test_12 |
subtask_01_12.txt |
test_13 |
subtask_01_13.txt |
test_14 |
subtask_01_14.txt |
test_15 |
subtask_01_15.txt |
test_16 |
subtask_01_16.txt |
test_17 |
subtask_01_17.txt |
test_18 |
subtask_01_18.txt |
test_19 |
subtask_01_19.txt |
test_20 |
subtask_01_20.txt |
test_21 |
subtask_01_21.txt |
test_22 |
subtask_01_22.txt |
test_23 |
subtask_01_23.txt |
test_24 |
subtask_01_24.txt |
test_25 |
subtask_01_25.txt |
test_26 |
subtask_01_26.txt |
test_27 |
subtask_01_27.txt |
test_28 |
subtask_01_28.txt |
test_29 |
subtask_01_29.txt |
test_30 |
subtask_01_30.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
47 ms |
98432 KB |
subtask_01_02.txt |
AC |
47 ms |
98432 KB |
subtask_01_03.txt |
AC |
47 ms |
98432 KB |
subtask_01_04.txt |
AC |
47 ms |
98432 KB |
subtask_01_05.txt |
AC |
47 ms |
98432 KB |
subtask_01_06.txt |
AC |
47 ms |
98432 KB |
subtask_01_07.txt |
AC |
47 ms |
98432 KB |
subtask_01_08.txt |
AC |
47 ms |
98432 KB |
subtask_01_09.txt |
AC |
47 ms |
98432 KB |
subtask_01_10.txt |
AC |
47 ms |
98432 KB |
subtask_01_11.txt |
AC |
47 ms |
98432 KB |
subtask_01_12.txt |
AC |
47 ms |
98432 KB |
subtask_01_13.txt |
AC |
47 ms |
98432 KB |
subtask_01_14.txt |
AC |
47 ms |
98432 KB |
subtask_01_15.txt |
AC |
47 ms |
98432 KB |
subtask_01_16.txt |
AC |
47 ms |
98432 KB |
subtask_01_17.txt |
AC |
47 ms |
98432 KB |
subtask_01_18.txt |
AC |
47 ms |
98432 KB |
subtask_01_19.txt |
AC |
47 ms |
98432 KB |
subtask_01_20.txt |
AC |
48 ms |
98432 KB |
subtask_01_21.txt |
AC |
47 ms |
98432 KB |
subtask_01_22.txt |
AC |
47 ms |
98432 KB |
subtask_01_23.txt |
AC |
47 ms |
98432 KB |
subtask_01_24.txt |
AC |
47 ms |
98432 KB |
subtask_01_25.txt |
AC |
47 ms |
98432 KB |
subtask_01_26.txt |
AC |
47 ms |
98432 KB |
subtask_01_27.txt |
AC |
47 ms |
98432 KB |
subtask_01_28.txt |
AC |
47 ms |
98432 KB |
subtask_01_29.txt |
AC |
47 ms |
98432 KB |
subtask_01_30.txt |
AC |
47 ms |
98432 KB |