Submission #1174084
Source Code Expand
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <random> #include <stdio.h> #include <string.h> using namespace std; int main() { int a[450], b[450], c[450], d[450]; int h, w, k, t; cin >> h >> w >> k >> t; for (int i = 0; i < k; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; a[i]--; b[i]--; c[i]--; d[i]--; } int p[30][30]; for (int y = 0; y < h; y++) { for (int x = 0; x < w; x++) { p[y][x] = -1; } } for (int i = 0; i < k; i++) { p[a[i]][b[i]] = i; } char *ss = new char[451 * t + 1]; mt19937_64 mt; for (int l = 0; l < t; l++) { char *s = ss + 451 * l; int u[450] = {}, n = 0; for (int y = 0; y < h; y++) { for (int x = 0; x < w; x++) { int i = p[y][x]; if (i < 0) continue; int dy = c[i] - y; int dx = d[i] - x; int m = 0b0000; // UDLR //if (mt() % 256 < max(1 - l, 0)) m = mt() & 0b1111; if (dy < 0) m |= 0b1000; if (dy > 0) m |= 0b0100; if (dx < 0) m |= 0b0010; if (dx > 0) m |= 0b0001; if (y == 0 || p[y - 1][x] != -1) m &= 0b0111; if (y == h - 1 || p[y + 1][x] != -1) m &= 0b1011; if (x == 0 || p[y][x - 1] != -1) m &= 0b1101; if (x == w - 1 || p[y][x + 1] != -1) m &= 0b1110; if (m == 0) { s[i] = '-'; } else { int z[4]; z[0] = (y < 5) - (y >= 25); z[1] = -z[0]; z[2] = (x < 5) - (x >= 25); z[3] = -z[2]; int j0 = mt() % 4, j2, js = -10; for (int j = 0; j < 4; j++) { int j1 = (j + j0) % 4; int jt = z[j1]; if ((m >> j1 & 1) && jt > js) { j2 = j1; js = jt; } } s[i] = "RLDU"[j2]; switch (s[i]) { case 'R': p[y][x + 1] = -2; break; case 'L': p[y][x - 1] = -2; break; case 'D': p[y + 1][x] = -2; break; case 'U': p[y - 1][x] = -2; break; } } } } for (int y = 0; y < h; y++) { for (int x = 0; x < w; x++) { int i = p[y][x]; if (i < 0 || u[i] || s[i] == '-') continue; switch (s[i]) { case 'R': p[y][x + 1] = i; break; case 'L': p[y][x - 1] = i; break; case 'D': p[y + 1][x] = i; break; case 'U': p[y - 1][x] = i; break; } p[y][x] = -1; u[i] = 1; n++; } } //for (int i = 0; i < k; i++) { // cout << (int)s[i] << " "; //} //cout << endl; s[k] = '\n'; if (n <= 1) { ss[l * 451] = 0; cout << l << '\n' << ss; cout << flush; break; } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - 日本橋大渋滞 |
User | merom686 |
Language | C++14 (GCC 5.4.1) |
Score | 4663 |
Code Size | 3443 Byte |
Status | AC |
Exec Time | 2 ms |
Memory | 256 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 | 160 / 50000 | 159 / 50000 | 156 / 50000 | 160 / 50000 | 171 / 50000 | 156 / 50000 | 153 / 50000 | 163 / 50000 | 148 / 50000 | 152 / 50000 | 166 / 50000 | 151 / 50000 | 147 / 50000 | 168 / 50000 | 149 / 50000 | 164 / 50000 | 155 / 50000 | 151 / 50000 | 154 / 50000 | 151 / 50000 | 167 / 50000 | 150 / 50000 | 157 / 50000 | 149 / 50000 | 148 / 50000 | 154 / 50000 | 156 / 50000 | 144 / 50000 | 155 / 50000 | 149 / 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 | 2 ms | 256 KB |
subtask_01_02.txt | AC | 2 ms | 256 KB |
subtask_01_03.txt | AC | 2 ms | 256 KB |
subtask_01_04.txt | AC | 2 ms | 256 KB |
subtask_01_05.txt | AC | 2 ms | 256 KB |
subtask_01_06.txt | AC | 2 ms | 256 KB |
subtask_01_07.txt | AC | 2 ms | 256 KB |
subtask_01_08.txt | AC | 2 ms | 256 KB |
subtask_01_09.txt | AC | 2 ms | 256 KB |
subtask_01_10.txt | AC | 2 ms | 256 KB |
subtask_01_11.txt | AC | 2 ms | 256 KB |
subtask_01_12.txt | AC | 2 ms | 256 KB |
subtask_01_13.txt | AC | 2 ms | 256 KB |
subtask_01_14.txt | AC | 2 ms | 256 KB |
subtask_01_15.txt | AC | 2 ms | 256 KB |
subtask_01_16.txt | AC | 2 ms | 256 KB |
subtask_01_17.txt | AC | 2 ms | 256 KB |
subtask_01_18.txt | AC | 2 ms | 256 KB |
subtask_01_19.txt | AC | 2 ms | 256 KB |
subtask_01_20.txt | AC | 2 ms | 256 KB |
subtask_01_21.txt | AC | 2 ms | 256 KB |
subtask_01_22.txt | AC | 2 ms | 256 KB |
subtask_01_23.txt | AC | 2 ms | 256 KB |
subtask_01_24.txt | AC | 2 ms | 256 KB |
subtask_01_25.txt | AC | 2 ms | 256 KB |
subtask_01_26.txt | AC | 2 ms | 256 KB |
subtask_01_27.txt | AC | 2 ms | 256 KB |
subtask_01_28.txt | AC | 2 ms | 256 KB |
subtask_01_29.txt | AC | 2 ms | 256 KB |
subtask_01_30.txt | AC | 2 ms | 256 KB |