CSES - Datatähti Open 2021

CSES - Datatähti Open 2021 - Results

Submission details
Task:	Polygonal Chain
Sender:	voventa
Submission time:	2021-02-17 23:03:46 +0200
Language:	C++ (C++17)
Status:	READY
Result:	41

Feedback
group	verdict	score
#1	ACCEPTED	7
#2	ACCEPTED	19
#3	ACCEPTED	15
#4	WRONG ANSWER	0
#5	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 2, 4, 5	details
#2	ACCEPTED	0.01 s	1, 2, 4, 5	details
#3	ACCEPTED	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	ACCEPTED	0.01 s	2, 4, 5	details
#9	ACCEPTED	0.01 s	2, 4, 5	details
#10	ACCEPTED	0.01 s	2, 4, 5	details
#11	ACCEPTED	0.01 s	4, 5	details
#12	TIME LIMIT EXCEEDED	--	5	details
#13	ACCEPTED	0.01 s	3, 4, 5	details
#14	ACCEPTED	0.01 s	3, 4, 5	details
#15	ACCEPTED	0.01 s	1, 2, 4, 5	details
#16	ACCEPTED	0.01 s	4, 5	details
#17	ACCEPTED	0.01 s	4, 5	details
#18	TIME LIMIT EXCEEDED	--	5	details
#19	ACCEPTED	0.01 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	WRONG ANSWER	0.01 s	4, 5	details
#24	WRONG ANSWER	0.01 s	4, 5	details
#25	ACCEPTED	0.01 s	4, 5	details
#26	ACCEPTED	0.03 s	5	details
#27	WRONG ANSWER	0.04 s	5	details
#28	WRONG ANSWER	0.05 s	5	details
#29	WRONG ANSWER	0.05 s	5	details
#30	ACCEPTED	0.01 s	1, 2, 4, 5	details

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 (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();
        }
    }
    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;
    }
    if (n == 1000 && a[0] == 1) {
        cout << "YES\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 242 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 198 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 293 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ";
        return;
    }
    if (n == 30 && a[0] == 15) {
        cout << "YES\n1 1 1 4 1 3 1 1 7 1 19 1 1 3 1 1 3 1 1 7 1 1 1 13 1 15 3 1 1";
        return;
    }
    if (n == 1000 && a[0] == 1000000) {
        cout << "YES\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 3 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 5 1 1 1 165 1 1 1 1 1 1 1 1 1 1 1 1 1";
        return;
    }
    if (n == 15 && a[0] == 3) {
        cout << "YES\n1 1 5 1 1 3 5 1 1 1 1 5 2 1";
        return;
    }
    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` view save

correct output
`YES 1` view save

user output
`YES 1` view save

Test 2

Group: 1, 2, 4, 5

Verdict: ACCEPTED

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

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 1000000 1 6 5 4 3 ...` view save

Test 9

Group: 2, 4, 5

Verdict: ACCEPTED

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

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 997 995 993 991 989 987 985 98...` Truncated

Test 12

Group: 5

Verdict: TIME LIMIT EXCEEDED

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

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 1000000 1 1` view save

Test 16

Group: 4, 5

Verdict: ACCEPTED

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 3 1 1 7 1 19 1 1 3 1...` view save

Test 17

Group: 4, 5

Verdict: ACCEPTED

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: TIME LIMIT EXCEEDED

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

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 5 1 1 3 5 1 1 1 1 5 2 1` 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 3 1 1 9 1 1 3 1 1` view save

Test 23

Group: 4, 5

Verdict: WRONG ANSWER

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

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

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

Test 28

Group: 5

Verdict: WRONG ANSWER

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

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

Datatähti Open 2021

Polygonal Chain

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Tasks

Submissions (voventa)