Task: | Polygonal Chain |
Sender: | MKopchev |
Submission time: | 2021-01-29 20:53:21 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
#4 | WRONG ANSWER | 0 |
#5 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
#2 | WRONG ANSWER | 0.28 s | 1, 2, 4, 5 | details |
#3 | WRONG ANSWER | 0.01 s | 1, 2, 4, 5 | details |
#4 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
#6 | ACCEPTED | 0.01 s | 2, 4, 5 | details |
#7 | ACCEPTED | 0.01 s | 2, 4, 5 | details |
#8 | WRONG ANSWER | 0.01 s | 2, 4, 5 | details |
#9 | ACCEPTED | 0.01 s | 2, 4, 5 | details |
#10 | TIME LIMIT EXCEEDED | -- | 2, 4, 5 | details |
#11 | WRONG ANSWER | 0.01 s | 4, 5 | details |
#12 | WRONG ANSWER | 0.02 s | 5 | details |
#13 | TIME LIMIT EXCEEDED | -- | 3, 4, 5 | details |
#14 | TIME LIMIT EXCEEDED | -- | 3, 4, 5 | details |
#15 | WRONG ANSWER | 0.01 s | 1, 2, 4, 5 | details |
#16 | ACCEPTED | 0.04 s | 4, 5 | details |
#17 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
#18 | TIME LIMIT EXCEEDED | -- | 5 | details |
#19 | ACCEPTED | 0.07 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.01 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 | TIME LIMIT EXCEEDED | -- | 5 | details |
#27 | TIME LIMIT EXCEEDED | -- | 5 | details |
#28 | TIME LIMIT EXCEEDED | -- | 5 | details |
#29 | TIME LIMIT EXCEEDED | -- | 5 | details |
#30 | ACCEPTED | 0.01 s | 1, 2, 4, 5 | details |
Compiler report
input/code.cpp: In function 'void go(int)': input/code.cpp:56:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation] for(int i=1;i<n;i++)cout<<outp[i]<<" ";cout<<endl; ^~~ input/code.cpp:56:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for' for(int i=1;i<n;i++)cout<<outp[i]<<" ";cout<<endl; ^~~~
Code
#include<bits/stdc++.h> using namespace std; const int nmax=2e5+5; int n; int outp[nmax]; int inp[nmax]; char dir[nmax]; pair<int,int> points[nmax][2]; bool in(int p,int q,int val) { if(p>q)swap(p,q); return p<=val&&val<=q; } bool meet(int p,int q,int u,int v) { if(p>q)swap(p,q); if(u>v)swap(u,v); return max(p,u)<=min(q,v); } void go(int pos) { points[pos][1]=points[pos][0]; if(pos%2)points[pos][1].first+=inp[pos]; else points[pos][1].first-=inp[pos]; /*test - | */ for(int j=1;j+1<pos;j++) { if(in(points[pos][0].first,points[pos][1].first,points[j][1].first)&&in(points[j][1].second,points[j+1][0].second,points[pos][0].second))return; } /* test - - */ for(int j=1;j<pos;j++) { if(points[pos][0].second==points[j][0].second&&meet(points[pos][0].first,points[pos][1].first,points[j][0].first,points[j][1].first))return; } if(pos==n) { cout<<"YES\n"; for(int i=1;i<n;i++)cout<<outp[i]<<" ";cout<<endl; exit(0); } for(outp[pos]=1;outp[pos]<=(1<<12);outp[pos]=outp[pos]<<1) { points[pos+1][0]=points[pos][1]; if(dir[pos]=='U')points[pos+1][0].second+=outp[pos]; else points[pos+1][0].second-=outp[pos]; /* test | - */ for(int i=1;i<pos;i++) { //meet p[i][0] - p[i][1] with p[j][1]-p[j+1][0] if(in(points[pos][1].second,points[pos+1][0].second,points[i][1].second)&&in(points[i][1].first,points[i][0].first,points[pos+1][0].first))return; } /* test | | */ for(int j=1;j<pos;j++) { if(points[pos][0].first==points[j][0].first&&meet(points[pos+1][0].second,points[pos][1].second,points[j+1][0].second,points[j][1].second))return; } go(pos+1); } } int main() { ios_base::sync_with_stdio(false); cin.tie(); cout.tie(); cin>>n; for(int i=1;i<=n;i++)cin>>inp[i]; for(int i=1;i<n;i++)cin>>dir[i]; go(1); cout<<"NO\n"; return 0; }
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: WRONG ANSWER
input |
---|
8 5 8 7 5 6 5 3 4 DUUUDDD |
correct output |
---|
YES 1 5 1 1 3 1 1 |
user output |
---|
NO |
Test 3
Group: 1, 2, 4, 5
Verdict: WRONG ANSWER
input |
---|
8 9 8 8 10 10 8 9 10 DDDUUUD |
correct output |
---|
YES 1 1 1 4 1 1 7 |
user output |
---|
NO |
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 4 |
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 2 4 1 1 1 1 1 4 1 1 8 1 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 4 1 1 1 1 1 8 1 16 1 32 1 |
Test 8
Group: 2, 4, 5
Verdict: WRONG ANSWER
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 |
---|
NO |
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 128 64 32 16 8 4 1 1 4 8 16 32... |
Test 10
Group: 2, 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
15 100 2 99 1 78 4 93 2 100 1 15 ... |
correct output |
---|
NO |
user output |
---|
(empty) |
Test 11
Group: 4, 5
Verdict: WRONG ANSWER
input |
---|
1000 999997 999995 999993 999991 99... |
correct output |
---|
YES 997 995 993 991 989 987 985 98... |
user output |
---|
NO |
Test 12
Group: 5
Verdict: WRONG ANSWER
input |
---|
100000 999999998 999999996 999999994 ... |
correct output |
---|
YES 99997 99995 99993 99991 99989 ... |
user output |
---|
NO |
Test 13
Group: 3, 4, 5
Verdict: TIME LIMIT EXCEEDED
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 |
---|
(empty) |
Test 14
Group: 3, 4, 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
NO |
user output |
---|
(empty) |
Test 15
Group: 1, 2, 4, 5
Verdict: WRONG ANSWER
input |
---|
5 6 7 7 6 6 UDUU |
correct output |
---|
YES 1 4 1 1 |
user output |
---|
NO |
Test 16
Group: 4, 5
Verdict: ACCEPTED
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 |
---|
YES 1 1 1 1 1 4 1 1 1 1 8 1 1 1 1 ... |
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 4 1 1 4 8 1 1 1 1 8 2 1 |
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 128 64 32 16 8 1 4 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 8 1 16 1 4 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: TIME LIMIT EXCEEDED
input |
---|
100000 209655 9167 9389 191291 198294... |
correct output |
---|
NO |
user output |
---|
(empty) |
Test 27
Group: 5
Verdict: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
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 2 1 1 8 16 32 |