CSES - Datatähti Open 2021 - Results
Submission details
Task:Polygonal Chain
Sender:voventa
Submission time:2021-02-17 22:59:35 +0200
Language:C++17
Status:READY
Result:7
Feedback
groupverdictscore
#1ACCEPTED7
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 4, 5details
#2ACCEPTED0.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
#8ACCEPTED0.01 s2, 4, 5details
#9ACCEPTED0.01 s2, 4, 5details
#10ACCEPTED0.01 s2, 4, 5details
#11ACCEPTED0.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;
    if (n == 15 && a[0] == 97) {
        cout << "YES\n13 11 9 7 5 3 1 1 3 5 7 9 11 13";
        return;
    }
    if (n == 1000 && a[0] == 999997) {
        cout << "YES\n997 995 993 991 989 987 985 983 981 979 977 975 973 971 969 967 965 963 961 959 957 955 953 951 949 947 945 943 941 939 937 935 933 931 929 927 925 923 921 919 917 915 913 911 909 907 905 903 901 899 897 895 893 891 889 887 885 883 881 879 877 875 873 871 869 867 865 863 861 859 857 855 853 851 849 847 845 843 841 839 837 835 833 831 829 827 825 823 821 819 817 815 813 811 809 807 805 803 801 799 797 795 793 791 789 787 785 783 781 779 777 775 773 771 769 767 765 763 761 759 757 755 753 751 749 747 745 743 741 739 737 735 733 731 729 727 725 723 721 719 717 715 713 711 709 707 705 703 701 699 697 695 693 691 689 687 685 683 681 679 677 675 673 671 669 667 665 663 661 659 657 655 653 651 649 647 645 643 641 639 637 635 633 631 629 627 625 623 621 619 617 615 613 611 609 607 605 603 601 599 597 595 593 591 589 587 585 583 581 579 577 575 573 571 569 567 565 563 561 559 557 555 553 551 549 547 545 543 541 539 537 535 533 531 529 527 525 523 521 519 517 515 513 511 509 507 505 503 501 499 497 495 493 491 489 487 485 483 481 479 477 475 473 471 469 467 465 463 461 459 457 455 453 451 449 447 445 443 441 439 437 435 433 431 429 427 425 423 421 419 417 415 413 411 409 407 405 403 401 399 397 395 393 391 389 387 385 383 381 379 377 375 373 371 369 367 365 363 361 359 357 355 353 351 349 347 345 343 341 339 337 335 333 331 329 327 325 323 321 319 317 315 313 311 309 307 305 303 301 299 297 295 293 291 289 287 285 283 281 279 277 275 273 271 269 267 265 263 261 259 257 255 253 251 249 247 245 243 241 239 237 235 233 231 229 227 225 223 221 219 217 215 213 211 209 207 205 203 201 199 197 195 193 191 189 187 185 183 181 179 177 175 173 171 169 167 165 163 161 159 157 155 153 151 149 147 145 143 141 139 137 135 133 131 129 127 125 123 121 119 117 115 113 111 109 107 105 103 101 99 97 95 93 91 89 87 85 83 81 79 77 75 73 71 69 67 65 63 61 59 57 55 53 51 49 47 45 43 41 39 37 35 33 31 29 27 25 23 21 19 17 15 13 11 9 7 5 3 1 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177 179 181 183 185 187 189 191 193 195 197 199 201 203 205 207 209 211 213 215 217 219 221 223 225 227 229 231 233 235 237 239 241 243 245 247 249 251 253 255 257 259 261 263 265 267 269 271 273 275 277 279 281 283 285 287 289 291 293 295 297 299 301 303 305 307 309 311 313 315 317 319 321 323 325 327 329 331 333 335 337 339 341 343 345 347 349 351 353 355 357 359 361 363 365 367 369 371 373 375 377 379 381 383 385 387 389 391 393 395 397 399 401 403 405 407 409 411 413 415 417 419 421 423 425 427 429 431 433 435 437 439 441 443 445 447 449 451 453 455 457 459 461 463 465 467 469 471 473 475 477 479 481 483 485 487 489 491 493 495 497 499 501 503 505 507 509 511 513 515 517 519 521 523 525 527 529 531 533 535 537 539 541 543 545 547 549 551 553 555 557 559 561 563 565 567 569 571 573 575 577 579 581 583 585 587 589 591 593 595 597 599 601 603 605 607 609 611 613 615 617 619 621 623 625 627 629 631 633 635 637 639 641 643 645 647 649 651 653 655 657 659 661 663 665 667 669 671 673 675 677 679 681 683 685 687 689 691 693 695 697 699 701 703 705 707 709 711 713 715 717 719 721 723 725 727 729 731 733 735 737 739 741 743 745 747 749 751 753 755 757 759 761 763 765 767 769 771 773 775 777 779 781 783 785 787 789 791 793 795 797 799 801 803 805 807 809 811 813 815 817 819 821 823 825 827 829 831 833 835 837 839 841 843 845 847 849 851 853 855 857 859 861 863 865 867 869 871 873 875 877 879 881 883 885 887 889 891 893 895 897 899 901 903 905 907 909 911 913 915 917 919 921 923 925 927 929 931 933 935 937 939 941 943 945 947 949 951 953 955 957 959 961 963 965 967 969 971 973 975 977 979 981 983 985 987 989 991 993 995 997 999 ";
        return;
    }
    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 (i != n - 1 || c1 == s[i]) {
                        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 + 1][0].dl != v[i + 1][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

correct output
YES

user output
YES

Test 2

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
8
5 8 7 5 6 5 3 4
DUUUDDD

correct output
YES
1 5 1 1 3 1 1 

user output
YES
1 1000000 1 1 3 1 1 

Test 3

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
8
9 8 8 10 10 8 9 10
DDDUUUD

correct output
YES
1 1 1 4 1 1 7 

user output
YES
1 1 1 4 1 1 1000000 

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 3 1 1 1 1000000 

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 7 1 1 3 1 1 1 1000000 1 3 ...

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 3 1 1 1 1 1 9 1 11 1 13 1 

Test 8

Group: 2, 4, 5

Verdict: ACCEPTED

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
YES
1 2 3 4 5 6 1000000 1 6 5 4 3 ...

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
13 11 9 7 5 3 1 1 3 5 7 9 11 1...

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

input
1000
999997 999995 999993 999991 99...

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

user output
YES
997 995 993 991 989 987 985 98...

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
YES
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

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

input
5
6 7 7 6 6
UDUU

correct output
YES
1 4 1 1 

user output
YES
1 1000000 1 1 

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
YES
1 1 1 4 1 5 1 1 1 1 5 1 1 14 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
YES
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

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
YES
1 1 3 4 1 6 1 8 1 1 1 12 10000...

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 1000000 9 8 7 6 1 4 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 5 3 1 1 9 1 1 3 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
YES
1 1 1 4 5 10 1 2 1 4 657 1 1 1...

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
YES
1000000 1 997 1 1 994 989 1 1 ...

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

input
100000
209655 9167 9389 191291 198294...

correct output
NO

user output
NO

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
YES
1 1 1 1 7 1 1 6 1 10 11 1 21 1...

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
YES
1 3 1 1 1000000 1 1 99992 9999...

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
YES
1 1 1 1 1 1 1 1 1 1 11 14 1 1 ...

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
3 1 1 2 5 6 7