— Dark mode

Datatähti Open 2021

Polygonal Chain

  • Start: N/A
  • End: N/A
CSES - Datatähti Open 2021 - Results
Submission details
Task:Polygonal Chain
Sender:voventa
Submission time:2021-02-17 20:00:07 +0200
Language:C++ (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
#3ACCEPTED0.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
#90.01 s2, 4, 5details
#10ACCEPTED0.01 s2, 4, 5details
#110.01 s4, 5details
#12--5details
#130.01 s3, 4, 5details
#14ACCEPTED0.01 s3, 4, 5details
#15ACCEPTED0.01 s1, 2, 4, 5details
#160.01 s4, 5details
#170.01 s4, 5details
#18--5details
#19ACCEPTED0.01 s1, 2, 4, 5details
#200.01 s2, 4, 5details
#21ACCEPTED0.01 s2, 4, 5details
#22ACCEPTED0.01 s2, 4, 5details
#230.01 s4, 5details
#240.01 s4, 5details
#25ACCEPTED0.01 s4, 5details
#26ACCEPTED0.03 s5details
#270.04 s5details
#280.05 s5details
#290.05 s5details
#30ACCEPTED0.01 s1, 2, 4, 5details

Code

#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(a) (int)a.size()
#define pb push_back
//#define int long long

using namespace std;
typedef long long ll;

void solve();

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
    return 0;
}

int a[100010];

pair <int, int> xx[100010];

string s;
struct node {
    int ind;
    char dl, dr;
};

vector <vector <node>> v;

vector <int> ans, ans2;


void solve() {
    int n, l = 0, r;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (i == 0) {
            r = a[i];
        } else {
            l = r;
            if (i % 2 == 1)
                r = l - a[i];
            else
                r = l + a[i];
        }
        xx[i] = {l, r};
    }
    cin >> s;
    int A, B, C;
    for (int i = 0; i < n; ++i) {
        if (i == n - 1) {
            v.pb({{i, s[i - 1], '#'}});
        } else if (i == 0) {
            v.pb({{i, '#', s[i]}});
        } else {
            v.pb({{i, s[i - 1], s[i]}});
        }
        while (sz(v) > 2) {
            char c1 = v[sz(v) - 3].back().dr, c2 = v[sz(v) - 2].back().dr;
            A = max({abs(xx[v[sz(v) - 3][0].ind].X - xx[v[sz(v) - 3].back().ind].Y), abs(xx[v[sz(v) - 3][0].ind].Y - xx[v[sz(v) - 3].back().ind].X), abs(xx[v[sz(v) - 3][0].ind].X - xx[v[sz(v) - 3].back().ind].X), abs(xx[v[sz(v) - 3][0].ind].Y - xx[v[sz(v) - 3].back().ind].Y)});
            B = max({abs(xx[v[sz(v) - 2][0].ind].X - xx[v[sz(v) - 2].back().ind].Y), abs(xx[v[sz(v) - 2][0].ind].Y - xx[v[sz(v) - 2].back().ind].X), abs(xx[v[sz(v) - 2][0].ind].X - xx[v[sz(v) - 2].back().ind].X), abs(xx[v[sz(v) - 2][0].ind].Y - xx[v[sz(v) - 2].back().ind].Y)});
            C = max({abs(xx[v[sz(v) - 1][0].ind].X - xx[v[sz(v) - 1].back().ind].Y), abs(xx[v[sz(v) - 1][0].ind].Y - xx[v[sz(v) - 1].back().ind].X), abs(xx[v[sz(v) - 1][0].ind].X - xx[v[sz(v) - 1].back().ind].X), abs(xx[v[sz(v) - 1][0].ind].Y - xx[v[sz(v) - 1].back().ind].Y)});
            if ((A < B && B < C) || (A < B && B > C) || (A > B && B > C) || (A == B && B > C) || (A < B && B == C)) {
                break;
            }
            if ((A == B && B == C) || (A > B && B == C) ) {
                if (c1 != c2) {
                    cout << "NO";
                    return;
                } else {
                    if (c1 == s[i] || i == n - 1) {
                        for (auto i : v[sz(v) - 2]) {
                            v[sz(v) - 3].pb(i);
                        }
                        for (auto i : v[sz(v) - 1]) {
                            v[sz(v) - 3].pb(i);
                        }
                        v.pop_back();
                        v.pop_back();
                        continue;
                    } else
                        break;
                }
            }
            if (c1 != c2) {
                cout << "NO";
                return;
            }
            for (auto i : v[sz(v) - 2]) {
                v[sz(v) - 3].pb(i);
            }
            for (auto i : v[sz(v) - 1]) {
                v[sz(v) - 3].pb(i);
            }
            v.pop_back();
            v.pop_back();
        }
    }
    int t = -1;
    for (int i = 1; i < sz(v); ++i) {
        int t1 = max({abs(xx[v[i - 1][0].ind].X - xx[v[i - 1].back().ind].Y), abs(xx[v[i - 1][0].ind].Y - xx[v[i - 1].back().ind].X), abs(xx[v[i - 1][0].ind].X - xx[v[i - 1].back().ind].X), abs(xx[v[i - 1][0].ind].Y - xx[v[i - 1].back().ind].Y)});
        int t2 = max({abs(xx[v[i][0].ind].X - xx[v[i].back().ind].Y), abs(xx[v[i][0].ind].Y - xx[v[i].back().ind].X), abs(xx[v[i][0].ind].X - xx[v[i].back().ind].X), abs(xx[v[i][0].ind].Y - xx[v[i].back().ind].Y)});
        if (t1 > t2) {
            t = i;
            break;
        }
    }
    if (t == -1) {
        bool f = false;
        for (int i = 0; i < sz(v); ++i) {
            int k = 0;
            for (auto j : v[i]) {
                if (j.dr == j.dl) {
                    ans.pb(1);
                } else {
                    if (f)
                        ans.pb(k + 1);
                    else
                        ans.pb(sz(ans) + 1);
                }
                k++;
            }
            if (sz(v[i]) > 1) {
                ans.pop_back();
                if (v[i].back().dl == v[i].back().dr) {
                    if (i != 0 && v[i][0].dl != v[i][0].dr) {
                        ans.pb(sz(ans) - sz(v[i]) + 2);
                    } else {
                        ans.pb(1);
                    }
                } else {
                    if (i != 0 && v[i][0].dl != v[i][0].dr) {
                        ans.pb(sz(v[i]));
                    } else {
                        ans.pb(sz(ans) + 1);
                    }
                }
            }
            if (i != sz(v) - 1 && sz(v[i + 1]) != 1 && v[i][0].dl != v[i][0].dr) {
                ans.back() += sz(v[i + 1]) - 1;
                f = true;
            } else
                f = false;
        }
    } else {
        bool f = false;
        for (int i = 0; i < t; ++i) {
            int k = 0;
            for (auto j : v[i]) {
                if (j.dr == j.dl) {
                    ans.pb(1);
                } else {
                    if (f)
                        ans.pb(k + 1);
                    else
                        ans.pb(sz(ans) + 1);
                }
                k++;
            }
            if (sz(v[i]) > 1) {
                ans.pop_back();
                if (v[i].back().dl == v[i].back().dr) {
                    if (i != 0 && v[i][0].dl != v[i][0].dr) {
                        ans.pb(sz(ans) - sz(v[i]) + 2);
                    } else {
                        ans.pb(1);
                    }
                } else {
                    if (i != 0 && v[i][0].dl != v[i][0].dr) {
                        ans.pb(sz(v[i]));
                    } else {
                        ans.pb(sz(ans) + 1);
                    }
                }
            }
            if (i != sz(v) - 1 && sz(v[i + 1]) != 1 && v[i + 1][0].dl != v[i + 1][0].dr) {
                ans.back() += sz(v[i + 1]) - 1;
                f = true;
            } else
                f = false;
        }
    }
    if (t != -1) {
        bool f = false;
        for (int i = sz(v) - 1; i >= t; --i) {
            for (int j = sz(v[i]) - 1; j >= 0; --j) {
                if (v[i][j].dr == v[i][j].dl) {
                    ans2.pb(1);
                } else {
                    if (f)
                        ans2.pb(j - (sz(v[i]) - 1) + 1);
                    else
                        ans2.pb(sz(ans2) + 1);
                }
            }
            if (sz(v[i]) > 1) {
                ans2.pop_back();
                if (v[i][0].dl == v[i][0].dr) {
                    if (i != sz(v) - 1 && v[i].back().dl != v[i].back().dr) {
                        ans2.pb(sz(ans2) - sz(v[i]) + 2);
                    } else {
                        ans2.pb(1);
                    }
                } else {
                    if (i != sz(v) - 1 && v[i].back().dl != v[i].back().dr) {
                        ans2.pb(sz(v[i]));
                    } else {
                        ans2.pb(sz(ans2) + 1);
                    }
                }
            }
            if (i != t && sz(v[i - 1]) != 1 && v[i - 1].back().dl != v[i - 1].back().dr) {
                ans2.back() += sz(v[i - 1]) - 1;
                f = true;
            } else
                f = false;
        }
    }
    if (sz(ans) > 0)
        ans.pop_back();
    if (sz(ans2) > 0)
        ans2.pop_back();
    reverse(ans2.begin(), ans2.end());
    cout << "YES\n";
    for (auto i : ans) {
        cout << i << " ";
    }
    if (t != -1) {
        cout << 1000000 << ' ';
        for (auto i : ans2) {
            cout << i << " ";
        }
    }
    return;
}

Test details

Test 1

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
2
2 10
D
view save

correct output
YES
1 
view save

user output
YES
1 
view save

Test 2

Group: 1, 2, 4, 5

Verdict:

input
8
5 8 7 5 6 5 3 4
DUUUDDD
view save

correct output
YES
1 5 1 1 3 1 1 
view save

user output
YES
1 2 1 1 1000000 1 1 
view save

Test 3

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
8
9 8 8 10 10 8 9 10
DDDUUUD
view save

correct output
YES
1 1 1 4 1 1 7 
view save

user output
YES
1 1 1 4 1 1 1000000 
view save

Test 4

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
8
9 10 8 8 9 9 7 8
DDDDUUU
view save

correct output
NO
view save

user output
NO
view save

Test 5

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
8
10 2 8 3 10 2 10 10
DDUUUUD
view save

correct output
YES
1 1 3 1 1 1 7 
view save

user output
YES
1 1 3 1 1 1 1000000 
view save

Test 6

Group: 2, 4, 5

Verdict: ACCEPTED

input
15
73 74 97 82 19 50 26 51 56 93 ...
view save

correct output
YES
1 2 3 1 1 3 1 1 1 10 1 3 1 1 
view save

user output
YES
1 2 7 1 1 3 1 1 1 1000000 1 3 ...
view save

Test 7

Group: 2, 4, 5

Verdict: ACCEPTED

input
15
95 71 97 77 98 76 100 62 96 69...
view save

correct output
YES
1 1 3 1 1 1 1 1 9 1 11 1 13 1 
view save

user output
YES
1 1 3 1 1 1 1 1 9 1 11 1 13 1 
view save

Test 8

Group: 2, 4, 5

Verdict:

input
15
79 81 84 86 88 90 92 92 91 89 ...
view save

correct output
YES
1 2 3 4 5 6 14 1 6 5 4 3 2 1 
view save

user output
YES
1 2 3 4 5 6 7 1000000 6 5 4 3 ...
view save

Test 9

Group: 2, 4, 5

Verdict:

input
15
97 90 87 83 79 76 74 23 24 76 ...
view save

correct output
YES
13 11 9 7 5 3 1 1 3 5 7 9 11 1...
view save

user output
YES
1 2 3 4 5 6 7 1 9 10 11 12 13 ...
view save

Test 10

Group: 2, 4, 5

Verdict: ACCEPTED

input
15
100 2 99 1 78 4 93 2 100 1 15 ...
view save

correct output
NO
view save

user output
NO
view save

Test 11

Group: 4, 5

Verdict:

input
1000
999997 999995 999993 999991 99...
view save

correct output
YES
997 995 993 991 989 987 985 98...
view save

user output
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Truncated

Test 12

Group: 5

Verdict:

input
100000
999999998 999999996 999999994 ...
view save

correct output
YES
99997 99995 99993 99991 99989 ...
view save

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 ...
view save

correct output
YES
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
view save

user output
YES
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
Truncated

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 ...
view save

correct output
NO
view save

user output
NO
view save

Test 15

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
5
6 7 7 6 6
UDUU
view save

correct output
YES
1 4 1 1 
view save

user output
YES
1 4 1 1 
view save

Test 16

Group: 4, 5

Verdict:

input
30
15 12 9 88 10 26 78 23 67 14 9...
view save

correct output
YES
1 1 1 4 1 3 1 1 7 1 19 1 1 3 1...
view save

user output
YES
1 1 1 4 1 5 1 1 1 1 5 1 1 14 1...
view save

Test 17

Group: 4, 5

Verdict:

input
1000
1000000 1 146324 146324 289287...
view save

correct output
YES
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
view save

user output
YES
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
Truncated

Test 18

Group: 5

Verdict:

input
100000
1000000000 1 421262579 4212625...
view save

correct output
YES
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
view save

user output
(empty)

Test 19

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
8
1 3 1 2 5 1 1 2
DUUUDUU
view save

correct output
NO
view save

user output
NO
view save

Test 20

Group: 2, 4, 5

Verdict:

input
15
3 1 33 13 1 11 32 8 1 19 15 25...
view save

correct output
YES
1 1 5 1 1 3 5 1 1 1 1 5 2 1 
view save

user output
YES
1 1 3 4 1 6 1 8 1 1 1 12 10000...
view save

Test 21

Group: 2, 4, 5

Verdict: ACCEPTED

input
15
10 2 39 41 42 34 31 28 26 24 2...
view save

correct output
YES
1 1 1 1 10 9 8 7 6 1 4 1 1 1 
view save

user output
YES
1 1 1 1 1000000 9 8 7 6 1 4 1 ...
view save

Test 22

Group: 2, 4, 5

Verdict: ACCEPTED

input
15
27 4 6 23 26 37 40 38 44 27 3 ...
view save

correct output
YES
1 1 1 1 5 1 7 1 3 1 1 3 1 1 
view save

user output
YES
1 1 1 1 5 1 7 1 9 1 1 5 1 1 
view save

Test 23

Group: 4, 5

Verdict:

input
1000
3246 3562 197273 197429 197755...
view save

correct output
YES
1 1 1 4 5 10 3 1 1 3 7 12 1 1 ...
view save

user output
YES
1 1 1 4 5 10 1 2 1 4 657 1 1 1...
Truncated

Test 24

Group: 4, 5

Verdict:

input
1000
503981 503487 503350 502673 50...
view save

correct output
YES
999 1 997 1 1 994 989 1 1 1 1 ...
view save

user output
YES
1000000 1 997 1 1 994 989 1 1 ...
Truncated

Test 25

Group: 4, 5

Verdict: ACCEPTED

input
1000
1445 1363 1749 1084 262408 263...
view save

correct output
NO
view save

user output
NO
view save

Test 26

Group: 5

Verdict: ACCEPTED

input
100000
209655 9167 9389 191291 198294...
view save

correct output
NO
view save

user output
NO
view save

Test 27

Group: 5

Verdict:

input
100000
16295 14904 5103 13337 26939 3...
view save

correct output
YES
1 1 1 1 5 6 1 1 1 10 11 1 13 1...
view save

user output
YES
3 1 1 1 7 1 1 6 1 10 11 1 21 1...
Truncated

Test 28

Group: 5

Verdict:

input
100000
1859 174288 15040 4631 4993844...
view save

correct output
YES
1 3 1 1 99997 99992 1 1 5 1 1 ...
view save

user output
YES
1 3 1 1 1000000 1 1 99992 9999...
Truncated

Test 29

Group: 5

Verdict:

input
100000
959817 958289 966165 922369 92...
view save

correct output
YES
1 1 1 1 1 1 1 1 1 1 11 14 1 1 ...
view save

user output
YES
1 1 1 1 1 1 1 1 1 1 11 14 1 1 ...
Truncated

Test 30

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
8
2 3 2 3 5 6 7 8
UDDDUDU
view save

correct output
YES
1 2 1 1 5 6 7 
view save

user output
YES
3 1 1 2 5 6 7 
view save

Tasks

A Greater Integers-B Split in Three-C Sorting-D Distances-E Programmers-F Polygonal Chain-

Submissions (voventa)

2021-02-17 23:05:32 742021-02-17 23:03:46 412021-02-17 23:02:28 262021-02-17 23:01:42 72021-02-17 22:59:35 72021-02-17 22:58:29 72021-02-17 22:57:59 02021-02-17 20:16:06 72021-02-17 20:10:34 02021-02-17 20:09:58 72021-02-17 20:06:09 72021-02-17 20:00:07 02021-02-17 19:57:36 72021-02-17 19:57:08 72021-02-17 19:56:32 02021-02-17 19:53:35 72021-02-17 19:50:17 02021-02-17 19:46:52 02021-02-17 19:31:39 02021-02-17 19:25:35 152021-02-17 19:24:55 152021-02-17 00:03:49 152021-02-17 00:02:12 152021-02-16 23:02:39 152021-02-16 22:58:14 222021-02-16 22:30:56 222021-02-16 22:30:13 152021-02-16 22:20:41 152021-02-16 22:11:22 152021-02-16 21:55:57 222021-02-16 21:08:00 152021-02-16 21:06:49 02021-02-16 21:05:41 222021-02-16 21:01:01 02021-02-16 20:48:56 02021-02-16 20:46:03 02021-02-16 20:37:30 02021-02-16 20:36:03 02021-02-16 20:31:51 02021-02-16 20:30:35 02021-02-16 20:15:24 72021-02-16 20:09:51 222021-02-16 20:08:36 152021-02-16 20:06:45 152021-02-16 20:06:10 152021-02-16 20:01:42 02021-02-16 19:56:33 02021-02-16 19:55:59 02021-02-13 21:10:53 02021-02-13 20:36:15 02021-02-12 18:43:25 02021-02-12 18:42:08 02021-02-12 18:40:20 02021-02-12 18:36:24 02021-02-12 18:35:02 02021-02-12 18:29:38 02021-02-12 18:29:25 02021-02-12 16:54:20 02021-02-12 16:44:42 02021-02-12 16:41:21 02021-02-12 16:32:40 02021-02-12 16:31:48 02021-02-12 16:29:20 02021-02-12 16:25:19 02021-02-12 16:21:35 02021-02-12 16:18:43 0