| Task: | Polygonal Chain |
| Sender: | MKopchev |
| Submission time: | 2021-01-29 20:53:05 +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.17 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.03 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.03 s | 4, 5 | details |
| #17 | TIME LIMIT EXCEEDED | -- | 4, 5 | details |
| #18 | TIME LIMIT EXCEEDED | -- | 5 | details |
| #19 | ACCEPTED | 0.05 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<<11);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 |
