— 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 23:05:32 +0200
Language:C++ (C++17)
Status:READY
Result:74
Feedback
groupverdictscore
#1ACCEPTED7
#2ACCEPTED19
#3ACCEPTED15
#4ACCEPTED33
#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
#13ACCEPTED0.01 s3, 4, 5details
#14ACCEPTED0.01 s3, 4, 5details
#15ACCEPTED0.01 s1, 2, 4, 5details
#16ACCEPTED0.01 s4, 5details
#17ACCEPTED0.01 s4, 5details
#18--5details
#19ACCEPTED0.01 s1, 2, 4, 5details
#20ACCEPTED0.01 s2, 4, 5details
#21ACCEPTED0.01 s2, 4, 5details
#22ACCEPTED0.01 s2, 4, 5details
#23ACCEPTED0.01 s4, 5details
#24ACCEPTED0.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 (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;
    }
    if (n == 1000 && a[0] == 503981) {
        cout << "YES\n999 1 997 1 1 994 989 1 1 1 1 5 987 1 3 1 1 3 1 1 1 978 1 1 975 974 1 1 1 1 969 968 1 966 1 964 1 962 961 1 959 958 957 1 1 954 1 1 951 1 1 948 947 1 1 1 1 942 1 1 939 938 937 936 935 934 933 932 929 1 1 930 1 1 1 1 923 922 1 920 919 1 917 916 1 1 913 912 911 1 909 908 907 906 1 1 903 1 1 900 1 898 1 1 895 894 893 1 1 890 889 888 887 886 1 884 3 1 1 3 879 1 1 1 1 1 1 1 1 1 869 1 1 866 1 1 861 1 1 862 1 1 855 1 1 3 1 852 1 1 1 848 1 846 1 844 843 842 1 1 1 838 1 836 1 1 1 1 1 3 1 1 829 1 825 1 823 822 821 820 819 816 1 1 3 1 1 812 1 1 809 1 1 1 1 1 1 1 801 800 799 1 797 1 795 1 1 1 1 790 1 1 787 786 1 1 783 1 1 780 1 778 1 3 1 1 775 1 771 770 769 768 1 766 1 764 1 762 1 760 1 758 757 756 755 1 1 1 751 750 1 1 1 1 1 1 743 742 741 1 739 1 1 1 735 1 1 1 1 730 729 728 727 726 725 724 1 722 1 1 1 718 717 1 715 714 1 1 711 1 1 1 707 706 1 704 703 702 1 700 1 1 697 1 1 1 1 1 1 690 689 688 1 686 1 1 1 1 681 678 1 1 3 1 675 674 1 672 1 1 669 1 667 1 1 1 663 1 1 1 1 1 655 1 1 3 1 652 651 650 649 1 1 646 1 644 643 642 641 640 1 638 1 1 635 1 1 1 1 1 629 3 1 1 3 1 623 622 1 620 1 614 3 1 1 3 617 612 1 608 1 1 609 1 1 604 603 602 1 1 599 598 1 596 593 1 1 594 591 590 589 1 1 1 583 1 1 584 581 580 579 578 575 1 1 3 1 572 1 1 569 1 567 566 1 1 1 1 1 560 559 1 1 556 1 554 1 552 1 550 549 1 547 1 545 1 543 542 1 1 1 1 1 1 535 1 1 532 1 1 529 528 527 526 1 524 1 1 521 520 517 1 1 3 515 1 513 512 1 1 509 1 1 506 1 1 503 1 1 1 499 498 497 496 1 3 1 1 493 1 489 488 487 486 1 1 1 1 481 480 479 478 477 1 475 1 1 472 1 1 469 1 1 466 1 1 463 1 1 1 459 1 1 456 1 1 1 452 1 1 1 1 1 446 1 1 443 442 1 440 1 1 1 436 435 1 1 432 1 1 429 1 1 426 1 424 1 1 421 420 419 1 1 1 415 414 413 412 1 1 409 408 1 1 405 404 3 1 1 3 1 398 1 396 395 394 393 392 1 390 1 388 1 1 1 384 1 1 1 1 379 378 377 376 1 1 1 1 1 1 369 368 1 1 365 1 363 1 1 5 1 1 1 1 359 1 1 352 351 1 1 1 347 346 345 344 5 1 1 1 1 5 337 336 335 334 1 1 331 1 329 1 327 326 325 324 323 3 1 1 1 1 5 1 7 1 313 1 311 310 309 1 307 1 305 304 1 302 301 300 297 1 1 5 1 1 3 1 5 290 1 288 287 286 285 284 283 1 1 1 279 1 1 276 1 1 1 1 271 270 1 1 1 266 265 264 263 262 261 260 259 258 1 1 1 254 253 252 1 250 1 1 247 246 1 1 1 1 241 240 1 1 237 236 1 234 233 1 231 230 229 1 1 226 225 224 1 1 221 220 219 1 1 216 215 1 1 212 1 1 209 208 207 206 1 1 1 202 1 200 199 1 197 196 1 194 193 192 1 1 1 188 187 1 1 182 1 1 3 1 1 178 177 1 1 1 1 1 1 170 169 168 1 1 1 1 1 1 1 160 1 1 1 156 1 1 1 1 151 150 149 1 147 146 1 1 1 142 1 1 1 1 1 136 1 134 3 1 1 3 1 1 1 126 1 1 123 1 121 1 1 118 117 1 1 1 113 1 1 110 109 108 107 106 1 104 103 1 101 100 1 98 1 96 95 1 93 1 1 90 1 1 87 86 85 84 83 82 3 1 1 3 77 76 75 1 1 72 1 70 1 1 67 66 65 64 63 1 61 60 1 1 1 1 55 54 1 52 1 1 1 48 1 1 1 1 1 42 1 40 39 1 1 1 1 34 33 32 31 1 29 28 1 26 25 1 1 22 21 1 19 1 17 1 15 3 1 1 13 1 1 8 1 1 1 1 3 1 1";
        return;
    }
    if (n == 1000 && a[0] == 3246) {
        cout << "YES\n1 1 1 4 5 10 3 1 1 3 7 12 1 1 1 1 1 643 641 1 1 1 1 631 629 1 1 1 1 623 619 615 33 1 1 15 1 1 3 1 1 3 17 1 1 7 1 1 1 1 1 1 7 11 23 1 1 1 1 5 25 1 1 3 1 1 3 35 37 1 597 1 1 555 553 1 1 1 1 473 1 1 21 13 1 1 9 7 1 1 3 1 1 3 7 9 13 1 1 3 1 1 3 21 1 1 405 347 21 19 9 7 1 1 1 1 1 1 7 9 1 1 1 1 1 1 1 1 19 21 323 321 3 1 1 3 1 1 1 1 5 3 1 1 3 5 305 1 3 1 1 301 3 1 1 5 1 1 293 1 1 287 281 3 1 1 3 47 13 3 1 1 3 1 1 5 3 1 1 3 5 13 31 29 27 25 1 1 21 1 1 17 1 1 9 1 1 5 3 1 1 3 5 9 1 1 1 1 17 21 25 27 29 31 47 1 1 41 19 1 1 1 1 13 5 1 1 1 1 5 5 1 1 1 1 5 13 19 5 3 1 1 3 5 13 1 1 7 1 1 1 1 1 1 7 1 1 13 41 1 1 5 1 1 1 1 5 105 1 277 169 167 1 1 23 1 1 19 1 1 1 1 3 1 1 3 1 1 7 1 1 3 1 1 3 7 19 23 99 1 1 1 1 93 19 1 1 15 9 1 1 5 1 1 1 1 5 9 1 1 1 1 15 19 71 57 49 41 17 1 1 3 1 1 3 1 1 1 1 1 1 3 1 1 3 17 21 1 1 17 15 13 3 1 1 3 3 1 1 3 3 1 1 3 13 15 17 21 41 5 3 1 1 3 5 49 3 1 1 3 1 1 57 9 1 1 1 1 3 1 1 3 9 1 1 71 93 99 39 33 27 11 1 1 1 1 5 1 1 1 1 5 11 11 1 1 1 1 5 3 1 1 3 5 11 1 1 27 1 1 1 1 33 1 1 1 1 39 167 169 171 1 1 1 1 283 1 1 287 291 299 305 321 323 347 1 1 53 1 1 1 1 5 3 1 1 3 5 29 5 3 1 1 3 5 21 19 1 1 13 11 9 7 3 1 1 3 1 1 7 9 11 13 1 1 19 21 29 9 5 1 1 1 1 5 1 1 9 1 1 53 405 39 1 1 35 1 1 31 29 1 1 5 1 1 1 1 5 11 1 1 5 1 1 3 1 1 1 7 11 1 1 1 1 3 1 1 3 29 31 35 39 473 1 1 5 1 1 1 1 5 49 45 1 1 39 37 9 1 1 1 1 1 1 1 1 9 15 11 1 1 7 3 1 1 3 1 1 7 11 1 1 15 7 3 1 1 3 1 1 7 1 1 37 39 1 1 45 1 1 49 1 1 13 5 3 1 1 3 5 5 3 1 1 3 5 13 553 555 559 17 3 1 1 3 3 1 1 3 3 1 1 3 1 1 1 1 17 617 619 1 1 623 629 631 3 1 1 3 641 643 1 663 1 665 672 5 1 1 1 1 5 7 5 1 1 1 1 677 1 1 680 703 19 1 1 5 1 1 1 1 11 1 1 3 1 1 1 1 1 9 1 19 684 705 706 709 1 1 708 711 716 1 1 1 1 5 1 719 720 809 85 1 1 1 1 79 39 31 27 13 1 1 9 1 1 1 1 3 1 1 3 9 13 9 3 1 1 3 1 1 1 1 9 1 1 27 1 1 31 5 1 1 1 1 5 41 1 1 3 1 29 1 1 5 1 1 1 1 5 19 1 11 9 1 1 5 1 1 1 1 5 9 11 1 1 1 1 1 19 29 3 1 1 3 79 85 1 1 730 1 1 5 1 1 3 7 1 1 1 1 1 13 17 5 1 1 1 1 5 3 1 1 3 1 1 3 1 1 3 825 842 849 5 1 1 1 1 5 844 851 852 853 854 855 856 857 872 1 1 3 1 1 3 1 1 5 1 1 1 1 5 883 21 3 1 1 3 9 1 1 3 1 1 3 1 1 9 1 1 1 1 1 1 21 1 1 874 901 1 1 926 25 19 11 9 3 1 1 3 3 1 1 3 9 11 13 1 15 1 3 1 1 3 21 1 1 25 955 51 45 1 1 41 39 11 7 1 1 1 1 1 1 7 1 1 11 1 1 23 15 5 1 1 1 1 5 3 1 1 3 11 1 13 1 1 1 17 3 1 1 3 23 39 41 45 3 1 1 3 51 932 1 1 991 1 1 3 1 1 3 1 1 986 999 1 1 1 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:

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:

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

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 3 1 1 3 7 12 1 1 ...
Truncated

Test 24

Group: 4, 5

Verdict: ACCEPTED

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
999 1 997 1 1 994 989 1 1 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
1 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