Task: | Polygonal Chain |
Sender: | lookcook |
Submission time: | 2021-01-30 20:34:36 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 26 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 7 |
#2 | ACCEPTED | 19 |
#3 | WRONG ANSWER | 0 |
#4 | TIME LIMIT EXCEEDED | 0 |
#5 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
#3 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
#4 | ACCEPTED | 0.81 s | 1, 2, 4, 5 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
#6 | ACCEPTED | 0.06 s | 2, 4, 5 | details |
#7 | ACCEPTED | 0.01 s | 2, 4, 5 | details |
#8 | ACCEPTED | 0.78 s | 2, 4, 5 | details |
#9 | ACCEPTED | 0.02 s | 2, 4, 5 | details |
#10 | ACCEPTED | 0.81 s | 2, 4, 5 | details |
#11 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
#12 | TIME LIMIT EXCEEDED | -- | 5 | details |
#13 | WRONG ANSWER | 0.81 s | 3, 4, 5 | details |
#14 | ACCEPTED | 0.81 s | 3, 4, 5 | details |
#15 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
#16 | WRONG ANSWER | 0.81 s | 4, 5 | details |
#17 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
#18 | TIME LIMIT EXCEEDED | -- | 5 | details |
#19 | ACCEPTED | 0.81 s | 1, 2, 4, 5 | details |
#20 | ACCEPTED | 0.01 s | 2, 4, 5 | details |
#21 | ACCEPTED | 0.01 s | 2, 4, 5 | details |
#22 | ACCEPTED | 0.24 s | 2, 4, 5 | details |
#23 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
#24 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
#25 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
#26 | RUNTIME ERROR | 0.01 s | 5 | details |
#27 | RUNTIME ERROR | 0.01 s | 5 | details |
#28 | RUNTIME ERROR | 0.01 s | 5 | details |
#29 | RUNTIME ERROR | 0.01 s | 5 | details |
#30 | ACCEPTED | 0.02 s | 1, 2, 4, 5 | details |
Code
#include <bits/stdc++.h> #define int long long using namespace std; int n; int a[1005]; string s; int res[1005]; map<pair<int,int>,int> vis; int x = 0; int y = 0; int start = 0; void rec(int pos) { if (( std::clock() - start ) / (double) CLOCKS_PER_SEC > 0.8) { cout << "NO\n"; exit(0); } if (pos == n) { cout << "YES\n"; for (int i = 1; i < n; i++) cout << res[i] << ' '; cout << '\n'; exit(0); } for (int f = 1; f < 15; f++) { int i = f; if (f%2==0) i = 20-f; res[pos] = i; bool ok = true; int v = 1; if (s[pos] == 'D') v = -1; for (int j = 0; j < res[pos]; j++) { y += v; if (vis.count({x,y})) ok = false; vis[{x,y}]++; } v = 1; if (pos%2==1) v = -1; for (int j = 0; j < a[pos]; j++) { x += v; if (vis.count({x,y})) ok = false; vis[{x,y}]++; } if (ok) { rec(pos + 1); } v = 1; if (pos%2==0) v = -1; for (int j = 0; j < a[pos]; j++) { vis[{x,y}]--; if (vis[{x,y}] == 0) vis.erase({x,y}); x += v; } v = 1; if (s[pos] == 'U') v = -1; for (int j = 0; j < res[pos]; j++) { vis[{x,y}]--; if (vis[{x,y}] == 0) vis.erase({x,y}); y += v; } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; cin >> s; s = "X" + s; x = a[0]; for (int i = 0; i <= x; i++) vis[{i,0}]++; start = std::clock(); rec(1); cout << "NO\n"; } /* */
Test details
Test 1
Group: 1, 2, 4, 5
Verdict: ACCEPTED
input |
---|
2 2 10 D |
correct output |
---|
YES 1 |
user output |
---|
YES 1 |
Test 2
Group: 1, 2, 4, 5
Verdict: ACCEPTED
input |
---|
8 5 8 7 5 6 5 3 4 DUUUDDD |
correct output |
---|
YES 1 5 1 1 3 1 1 |
user output |
---|
YES 1 18 1 1 3 1 1 |
Test 3
Group: 1, 2, 4, 5
Verdict: ACCEPTED
input |
---|
8 9 8 8 10 10 8 9 10 DDDUUUD |
correct output |
---|
YES 1 1 1 4 1 1 7 |
user output |
---|
YES 1 1 1 18 1 1 3 |
Test 4
Group: 1, 2, 4, 5
Verdict: ACCEPTED
input |
---|
8 9 10 8 8 9 9 7 8 DDDDUUU |
correct output |
---|
NO |
user output |
---|
NO |
Test 5
Group: 1, 2, 4, 5
Verdict: ACCEPTED
input |
---|
8 10 2 8 3 10 2 10 10 DDUUUUD |
correct output |
---|
YES 1 1 3 1 1 1 7 |
user output |
---|
YES 1 1 1 1 1 1 18 |
Test 6
Group: 2, 4, 5
Verdict: ACCEPTED
input |
---|
15 73 74 97 82 19 50 26 51 56 93 ... |
correct output |
---|
YES 1 2 3 1 1 3 1 1 1 10 1 3 1 1 |
user output |
---|
YES 1 18 18 1 1 1 1 1 1 18 18 18 1... |
Test 7
Group: 2, 4, 5
Verdict: ACCEPTED
input |
---|
15 95 71 97 77 98 76 100 62 96 69... |
correct output |
---|
YES 1 1 3 1 1 1 1 1 9 1 11 1 13 1 |
user output |
---|
YES 1 1 18 1 1 1 1 1 18 18 1 1 18 ... |
Test 8
Group: 2, 4, 5
Verdict: ACCEPTED
input |
---|
15 79 81 84 86 88 90 92 92 91 89 ... |
correct output |
---|
YES 1 2 3 4 5 6 14 1 6 5 4 3 2 1 |
user output |
---|
YES 1 3 5 6 7 16 18 1 16 7 6 5 3 1... |
Test 9
Group: 2, 4, 5
Verdict: ACCEPTED
input |
---|
15 97 90 87 83 79 76 74 23 24 76 ... |
correct output |
---|
YES 13 11 9 7 5 3 1 1 3 5 7 9 11 1... |
user output |
---|
YES 18 16 14 7 5 3 1 1 3 5 7 9 16 ... |
Test 10
Group: 2, 4, 5
Verdict: ACCEPTED
input |
---|
15 100 2 99 1 78 4 93 2 100 1 15 ... |
correct output |
---|
NO |
user output |
---|
NO |
Test 11
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 999997 999995 999993 999991 99... |
correct output |
---|
YES 997 995 993 991 989 987 985 98... |
user output |
---|
(empty) |
Test 12
Group: 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 999999998 999999996 999999994 ... |
correct output |
---|
YES 99997 99995 99993 99991 99989 ... |
user output |
---|
(empty) |
Test 13
Group: 3, 4, 5
Verdict: WRONG ANSWER
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
YES 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
NO |
Test 14
Group: 3, 4, 5
Verdict: ACCEPTED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
NO |
user output |
---|
NO |
Test 15
Group: 1, 2, 4, 5
Verdict: ACCEPTED
input |
---|
5 6 7 7 6 6 UDUU |
correct output |
---|
YES 1 4 1 1 |
user output |
---|
YES 1 18 1 1 |
Test 16
Group: 4, 5
Verdict: WRONG ANSWER
input |
---|
30 15 12 9 88 10 26 78 23 67 14 9... |
correct output |
---|
YES 1 1 1 4 1 3 1 1 7 1 19 1 1 3 1... |
user output |
---|
NO |
Test 17
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1000000 1 146324 146324 289287... |
correct output |
---|
YES 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
(empty) |
Test 18
Group: 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 1000000000 1 421262579 4212625... |
correct output |
---|
YES 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
user output |
---|
(empty) |
Test 19
Group: 1, 2, 4, 5
Verdict: ACCEPTED
input |
---|
8 1 3 1 2 5 1 1 2 DUUUDUU |
correct output |
---|
NO |
user output |
---|
NO |
Test 20
Group: 2, 4, 5
Verdict: ACCEPTED
input |
---|
15 3 1 33 13 1 11 32 8 1 19 15 25... |
correct output |
---|
YES 1 1 5 1 1 3 5 1 1 1 1 5 2 1 |
user output |
---|
YES 1 1 18 1 1 18 18 1 1 1 1 18 18... |
Test 21
Group: 2, 4, 5
Verdict: ACCEPTED
input |
---|
15 10 2 39 41 42 34 31 28 26 24 2... |
correct output |
---|
YES 1 1 1 1 10 9 8 7 6 1 4 1 1 1 |
user output |
---|
YES 1 1 1 1 18 16 14 12 7 1 5 1 1 ... |
Test 22
Group: 2, 4, 5
Verdict: ACCEPTED
input |
---|
15 27 4 6 23 26 37 40 38 44 27 3 ... |
correct output |
---|
YES 1 1 1 1 5 1 7 1 3 1 1 3 1 1 |
user output |
---|
YES 1 1 1 1 16 1 18 1 18 1 1 1 1 1... |
Test 23
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 3246 3562 197273 197429 197755... |
correct output |
---|
YES 1 1 1 4 5 10 3 1 1 3 7 12 1 1 ... |
user output |
---|
(empty) |
Test 24
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 503981 503487 503350 502673 50... |
correct output |
---|
YES 999 1 997 1 1 994 989 1 1 1 1 ... |
user output |
---|
(empty) |
Test 25
Group: 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1445 1363 1749 1084 262408 263... |
correct output |
---|
NO |
user output |
---|
(empty) |
Test 26
Group: 5
Verdict: RUNTIME ERROR
input |
---|
100000 209655 9167 9389 191291 198294... |
correct output |
---|
NO |
user output |
---|
(empty) |
Test 27
Group: 5
Verdict: RUNTIME ERROR
input |
---|
100000 16295 14904 5103 13337 26939 3... |
correct output |
---|
YES 1 1 1 1 5 6 1 1 1 10 11 1 13 1... |
user output |
---|
(empty) |
Test 28
Group: 5
Verdict: RUNTIME ERROR
input |
---|
100000 1859 174288 15040 4631 4993844... |
correct output |
---|
YES 1 3 1 1 99997 99992 1 1 5 1 1 ... |
user output |
---|
(empty) |
Test 29
Group: 5
Verdict: RUNTIME ERROR
input |
---|
100000 959817 958289 966165 922369 92... |
correct output |
---|
YES 1 1 1 1 1 1 1 1 1 1 11 14 1 1 ... |
user output |
---|
(empty) |
Test 30
Group: 1, 2, 4, 5
Verdict: ACCEPTED
input |
---|
8 2 3 2 3 5 6 7 8 UDDDUDU |
correct output |
---|
YES 1 2 1 1 5 6 7 |
user output |
---|
YES 1 3 1 1 14 16 18 |