CSES - Datatähti Open 2021 - Results
Submission details
Task:Polygonal Chain
Sender:MKopchev
Submission time:2021-01-29 20:52:47 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 4, 5details
#20.09 s1, 2, 4, 5details
#30.01 s1, 2, 4, 5details
#4ACCEPTED0.01 s1, 2, 4, 5details
#5ACCEPTED0.01 s1, 2, 4, 5details
#6ACCEPTED0.01 s2, 4, 5details
#7ACCEPTED0.01 s2, 4, 5details
#80.01 s2, 4, 5details
#9ACCEPTED0.01 s2, 4, 5details
#10--2, 4, 5details
#110.01 s4, 5details
#120.02 s5details
#13--3, 4, 5details
#14--3, 4, 5details
#150.01 s1, 2, 4, 5details
#16ACCEPTED0.02 s4, 5details
#17--4, 5details
#18--5details
#19ACCEPTED0.03 s1, 2, 4, 5details
#20ACCEPTED0.01 s2, 4, 5details
#21ACCEPTED0.01 s2, 4, 5details
#22ACCEPTED0.01 s2, 4, 5details
#23--4, 5details
#24--4, 5details
#25--4, 5details
#26--5details
#27--5details
#28--5details
#29--5details
#30ACCEPTED0.01 s1, 2, 4, 5details

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<<10);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

user output
YES

Test 2

Group: 1, 2, 4, 5

Verdict:

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:

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:

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:

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:

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:

input
100000
999999998 999999996 999999994 ...

correct output
YES
99997 99995 99993 99991 99989 ...

user output
NO

Test 13

Group: 3, 4, 5

Verdict:

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:

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:

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:

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:

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:

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:

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:

input
1000
1445 1363 1749 1084 262408 263...

correct output
NO

user output
(empty)

Test 26

Group: 5

Verdict:

input
100000
209655 9167 9389 191291 198294...

correct output
NO

user output
(empty)

Test 27

Group: 5

Verdict:

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:

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:

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