Submission #1173986
Source Code Expand
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<vector>
#include<random>
using namespace std;
using uint = unsigned int;
using ll = long long;
const int M = 1e9 + 7;
const ll MLL = 1e18L + 9;
#pragma unused(M)
#pragma unused(MLL)
#ifdef LOCAL
#include"rprint.hpp"
#else
template <class... T> void printl(T&&...){ }
template <class... T> void printc(T&&...){ }
template <class... T> void prints(T&&...){ }
template <class... T> void printd(T&&...){ }
#endif
int main(){
random_device rd;
mt19937 mt(rd());
int h, w, k, t;
cin >> h >> w >> k >> t;
vector<vector<int>> board(h, vector<int> (w));
vector<pair<int, int>> abs(k), cds(k);
for(int i=0;i<k;i++){
int a, b, c, d;
cin >> a >> b >> c >> d;
a--; b--; c--; d--;
abs[i] = {a, b};
cds[i] = {c, d};
board[a][b] = 1;
}
int ss = 0;
string out;
for(int i=0;i<t;i++){
vector<pair<int, int>> poss = abs;
int cnt = 0;
if(ss % 30 != 0){
for(int i=0;i<k;i++){
bool done = false;
if(abs[i] != cds[i] && mt() % 100 < 20){
int y = abs[i].first, x = abs[i].second;
vector<int> four(4);
iota(four.begin(), four.end(), 0);
shuffle(four.begin(), four.end(), mt);
for(int jj=0;jj<4;jj++){
int j = four[jj];
int ny = y + (j == 0 ? 1 : j == 1 ? -1 : 0), nx = x + (j == 2 ? 1 : j == 3 ? -1 : 0);
if(0 <= ny && ny < h && 0 <= nx && nx < w && !board[ny][nx]){
out += (j == 0 ? 'D' : j == 1 ? 'U' : j == 2 ? 'R' : 'L');
board[ny][nx] = 1;
abs[i] = {ny, nx};
done = true;
break;
}
}
}
if(!done){
out += '-';
poss[i] = {-1, -1};
}
}
ss++;
}else{
for(int i=0;i<k;i++){
int y = abs[i].first, x = abs[i].second;
if(y < cds[i].first){
int ny = y + 1, nx = x;
if(0 <= ny && ny < h && 0 <= nx && nx < w && !board[ny][nx]){
out += 'D';
board[ny][nx] = 1;
abs[i] = {ny, nx};
continue;
}
}
if(y > cds[i].first){
int ny = y - 1, nx = x;
if(0 <= ny && ny < h && 0 <= nx && nx < w && !board[ny][nx]){
out += 'U';
board[ny][nx] = 1;
abs[i] = {ny, nx};
continue;
}
}
if(x < cds[i].second){
int ny = y, nx = x + 1;
if(0 <= ny && ny < h && 0 <= nx && nx < w && !board[ny][nx]){
out += 'R';
board[ny][nx] = 1;
abs[i] = {ny, nx};
continue;
}
}
if(x > cds[i].second){
int ny = y, nx = x - 1;
if(0 <= ny && ny < h && 0 <= nx && nx < w && !board[ny][nx]){
out += 'L';
board[ny][nx] = 1;
abs[i] = {ny, nx};
continue;
}
}
out += '-';
poss[i] = {-1, -1};
cnt++;
}
}
out += '\n';
int diff = 0;
for(int i=0;i<k;i++){
diff += ::abs(abs[i].first - cds[i].first) + ::abs(abs[i].second - cds[i].second);
}
if(cnt == k){
if(i > t - 100 || diff < 1500){
cout << i + 1 << '\n';
cout << out << endl;
return 0;
}
ss++;
}
// prints(board);
for(int i=0;i<k;i++){
if(poss[i].first != -1){
board[poss[i].first][poss[i].second] = 0;
}
}
// prints(board);
// prints(abs);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
sumoooru |
Language |
C++14 (Clang 3.8.0) |
Score |
6622 |
Code Size |
4643 Byte |
Status |
AC |
Exec Time |
67 ms |
Memory |
5228 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 |
221 / 50000 |
297 / 50000 |
267 / 50000 |
260 / 50000 |
127 / 50000 |
220 / 50000 |
231 / 50000 |
225 / 50000 |
211 / 50000 |
232 / 50000 |
236 / 50000 |
239 / 50000 |
259 / 50000 |
264 / 50000 |
220 / 50000 |
202 / 50000 |
213 / 50000 |
224 / 50000 |
188 / 50000 |
256 / 50000 |
213 / 50000 |
175 / 50000 |
158 / 50000 |
125 / 50000 |
212 / 50000 |
157 / 50000 |
279 / 50000 |
211 / 50000 |
205 / 50000 |
295 / 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 |
34 ms |
2160 KB |
subtask_01_02.txt |
AC |
22 ms |
1524 KB |
subtask_01_03.txt |
AC |
26 ms |
1780 KB |
subtask_01_04.txt |
AC |
28 ms |
1780 KB |
subtask_01_05.txt |
AC |
64 ms |
4332 KB |
subtask_01_06.txt |
AC |
35 ms |
2160 KB |
subtask_01_07.txt |
AC |
33 ms |
2032 KB |
subtask_01_08.txt |
AC |
33 ms |
2160 KB |
subtask_01_09.txt |
AC |
38 ms |
2288 KB |
subtask_01_10.txt |
AC |
33 ms |
2032 KB |
subtask_01_11.txt |
AC |
31 ms |
2160 KB |
subtask_01_12.txt |
AC |
32 ms |
2032 KB |
subtask_01_13.txt |
AC |
28 ms |
1780 KB |
subtask_01_14.txt |
AC |
27 ms |
1780 KB |
subtask_01_15.txt |
AC |
35 ms |
2160 KB |
subtask_01_16.txt |
AC |
37 ms |
2416 KB |
subtask_01_17.txt |
AC |
38 ms |
2416 KB |
subtask_01_18.txt |
AC |
35 ms |
2160 KB |
subtask_01_19.txt |
AC |
43 ms |
2672 KB |
subtask_01_20.txt |
AC |
28 ms |
1780 KB |
subtask_01_21.txt |
AC |
35 ms |
2288 KB |
subtask_01_22.txt |
AC |
47 ms |
2928 KB |
subtask_01_23.txt |
AC |
51 ms |
3184 KB |
subtask_01_24.txt |
AC |
67 ms |
5228 KB |
subtask_01_25.txt |
AC |
36 ms |
2288 KB |
subtask_01_26.txt |
AC |
50 ms |
3184 KB |
subtask_01_27.txt |
AC |
25 ms |
1652 KB |
subtask_01_28.txt |
AC |
38 ms |
2288 KB |
subtask_01_29.txt |
AC |
37 ms |
2416 KB |
subtask_01_30.txt |
AC |
23 ms |
1524 KB |