CSES - Datatähti Open 2021 - Results
Submission details
Task:Polygonal Chain
Sender:apostoldaniel854
Submission time:2021-01-30 00:26:36 +0200
Language:C++17
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 4, 5details
#20.01 s1, 2, 4, 5details
#30.01 s1, 2, 4, 5details
#4ACCEPTED0.01 s1, 2, 4, 5details
#50.01 s1, 2, 4, 5details
#60.01 s2, 4, 5details
#7ACCEPTED0.01 s2, 4, 5details
#80.01 s2, 4, 5details
#90.01 s2, 4, 5details
#10ACCEPTED0.01 s2, 4, 5details
#110.04 s4, 5details
#12--5details
#130.04 s3, 4, 5details
#14ACCEPTED0.04 s3, 4, 5details
#150.01 s1, 2, 4, 5details
#160.01 s4, 5details
#170.04 s4, 5details
#18--5details
#19ACCEPTED0.01 s1, 2, 4, 5details
#200.01 s2, 4, 5details
#21ACCEPTED0.01 s2, 4, 5details
#220.01 s2, 4, 5details
#230.04 s4, 5details
#240.04 s4, 5details
#25ACCEPTED0.04 s4, 5details
#26--5details
#27--5details
#28--5details
#29--5details
#300.01 s1, 2, 4, 5details

Code

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
const int MAX_N = 1e5;
int length_ver[1 + MAX_N], length_hor[1 + MAX_N];


struct Segment {
    pair <int, int> a;
    pair <int, int> b;
};

#define Point pair <int, int>
#define x first
#define y second
bool onSegment(Point p, Point q, Point r)  {
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
        q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
       return true;

    return false;
}
int orientation(Point p, Point q, Point r)
{
    ll val = 1ll * (q.y - p.y) * (r.x - q.x) -
              1ll * (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;

    return (val > 0)? 1: 2;
}

bool doIntersect (Point p1, Point q1, Point p2, Point q2) {
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    if (o1 != o2 && o3 != o4)
        return true;
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;
    return false;
}


int main () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> length_ver[i];
    string direction;
    cin >> direction;
    direction = " " + direction;
    for (int i = 1; i < n; i++)
        length_hor[i] = (1 << (30 - i));
    vector <pair <int, int>> points;
    points.pb ({0, 0});
    pair <int, int> cur_point = {0, 0};
    for (int i = 1; i <= n; i++) {
        int ori;
        if (i % 2)
            ori = 1;
        else
            ori = -1;
        cur_point.second += ori * length_ver[i];
        points.pb (cur_point);
        if (i < n) {
            if (direction[i] == 'U')
                ori = 1;
            else
                ori = -1;
            cur_point.first += ori * length_hor[i];
            points.pb (cur_point);
        }
    }
    int sz = points.size ();
    vector <Segment> segments;
    for (int i = 0; i + 1 < sz; i++)
        segments.pb ({points[i], points[i + 1]});
    int nr_segments = segments.size ();
    for (Segment s : segments) {
       /// cout << s.a.first << " " << s.a.second << " " << s.b.first << " " << s.b.second << "\n";
        if (s.a.first == s.b.first) { /// x equal
            if (s.a.second > s.b.second)
                swap (s.a, s.b);
        }
        else {
            if (s.a.first > s.b.first) /// y equal
                swap (s.a, s.b);
        }
    }
    bool ok = true;
    for (int i = 0; i < nr_segments; i++)
        for (int j = i + 2; j < nr_segments; j++)
            if (doIntersect (segments[i].a, segments[i].b, segments[j].a, segments[j].b))
                ok = false;
    if (ok) {
        cout << "YES\n";
        for (int i = 1; i < n; i++)
            cout << length_hor[i] << " ";
        cout << "\n";
    }
    else {
        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
536870912 

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:

input
8
10 2 8 3 10 2 10 10
DDUUUUD

correct output
YES
1 1 3 1 1 1 7 

user output
NO

Test 6

Group: 2, 4, 5

Verdict:

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
NO

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
536870912 268435456 134217728 ...

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:

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
NO

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:

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
(empty)

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
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:

input
5
6 7 7 6 6
UDUU

correct output
YES
1 4 1 1 

user output
NO

Test 16

Group: 4, 5

Verdict:

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:

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
NO

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:

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
NO

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
536870912 268435456 134217728 ...

Test 22

Group: 2, 4, 5

Verdict:

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
NO

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
NO

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
NO

Test 25

Group: 4, 5

Verdict: ACCEPTED

input
1000
1445 1363 1749 1084 262408 263...

correct output
NO

user output
NO

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:

input
8
2 3 2 3 5 6 7 8
UDDDUDU

correct output
YES
1 2 1 1 5 6 7 

user output
NO