QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#90840	#5526. Jewel of Data Structure Problems	Sorting^#	AC ✓	97ms	4480kb	C++	2.2kb	2023-03-25 17:24:26	2023-03-25 17:24:30

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-25 17:24:30]
评测

测评结果：AC
用时：97ms
内存：4480kb

查看

[2023-03-25 17:24:26]
提交

answer

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ; 
typedef vector<int> vi;
typedef vector < long long > vl ;
typedef unsigned int uint ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAXN = 2e5 + 7 ;

int n , q ;
int a[ MAXN ] ;

bool used[ MAXN ] ;
int cnt_eq = 0 ;

int freq[ 2 ][ 2 ] , tot[ 2 ] ;

void rem ( int val , int pos ) {
    if ( val == pos ) { -- cnt_eq ; }
    -- freq[ ( val % 2 ) ][ ( pos % 2 ) ] ;
}
void add ( int val , int pos ) {
    if ( val == pos ) { ++ cnt_eq ; }
    ++ freq[ ( val % 2 ) ][ ( pos % 2 ) ] ;
}

void solve ( ) {
    cin >> n >> q ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
    }
    int cycles = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( used[ i ] == false ) {
            ++ cycles ;
            int x = i ;
            while ( used[ x ] == false ) {
                used[ x ] = true ;
                x = a[ x ] ;
            }
        }
    }
    tot[ 0 ] = n / 2 ;
    tot[ 1 ] = ( n + 1 ) / 2 ;
    cycles %= 2 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( a[ i ] == i ) { ++ cnt_eq ; }
        ++ freq[ ( a[ i ] % 2 ) ][ ( i % 2 ) ] ;
    }
    while ( q -- ) {
        cycles ^= 1 ;
        int x , y ; cin >> x >> y ;
        rem ( a[ x ] , x ) ; rem ( a[ y ] , y ) ;
        swap ( a[ x ] , a[ y ] ) ;
        add ( a[ x ] , x ) ; add ( a[ y ] , y ) ;
        if ( cnt_eq == n ) { cout << "-1\n" ; }
        else {
            if ( cycles != ( n % 2 ) ) { cout << n << "\n" ; }
            else if ( freq[ 0 ][ 0 ] == tot[ 0 ] && freq[ 1 ][ 1 ] == tot[ 1 ] ) {
                cout << n - 2 << "\n" ;
            }
            else {
                cout << n - 1 << "\n" ;
            }
        }
    }
}

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

Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3324kb

input:

output:

result:

ok 6 numbers

Test #2:

score: 0

Accepted

time: 26ms

memory: 3356kb

input:

output:

2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
...

result:

ok 200000 numbers

Test #3:

score: 0

Accepted

time: 50ms

memory: 3360kb

input:

output:

result:

ok 200000 numbers

Test #4:

score: 0

Accepted

time: 36ms

memory: 3356kb

input:

output:

result:

ok 200000 numbers

Test #5:

score: 0

Accepted

time: 36ms

memory: 3508kb

input:

output:

result:

ok 200000 numbers

Test #6:

score: 0

Accepted

time: 29ms

memory: 3508kb

input:

6 200000
4 2 5 3 6 1
1 2
4 6
5 4
1 6
6 5
4 2
5 3
6 2
6 5
1 4
6 3
6 5
2 3
4 5
4 1
3 6
5 6
2 4
3 2
2 3
6 1
1 3
1 3
3 6
1 6
2 5
3 4
1 4
4 1
4 6
3 5
6 2
6 5
4 1
5 6
5 4
1 6
2 4
6 3
1 3
5 2
1 6
1 3
1 3
3 6
6 5
3 2
6 4
6 4
3 2
3 1
5 3
6 3
6 5
3 5
2 5
4 2
1 5
1 2
3 4
3 2
4 6
3 5
2 1
5 4
1 4
5 3
1 5
5 4
3 1...

output:

result:

ok 200000 numbers

Test #7:

score: 0

Accepted

time: 34ms

memory: 3348kb

input:

7 200000
6 1 3 4 5 2 7
7 4
5 2
6 1
3 4
3 1
5 3
7 2
6 4
2 5
5 6
6 2
1 7
3 4
6 2
7 4
3 1
4 5
5 6
6 3
4 1
6 1
7 1
5 7
1 3
4 1
5 4
5 7
2 1
6 4
7 5
3 1
4 1
4 2
4 3
5 6
4 2
1 6
3 2
2 6
3 4
1 6
4 5
1 2
1 5
3 1
4 6
3 4
1 4
7 5
2 7
2 5
1 7
3 2
3 5
2 5
6 2
6 7
1 2
2 7
1 2
3 1
1 4
5 2
6 4
6 1
3 6
6 4
4 2
6 2
2...

output:

result:

ok 200000 numbers

Test #8:

score: 0

Accepted

time: 27ms

memory: 3420kb

input:

8 200000
5 4 7 1 6 2 8 3
8 4
5 3
2 6
5 3
3 5
1 6
3 4
5 3
1 3
1 2
6 3
8 7
8 3
3 8
6 4
3 4
3 7
6 4
4 2
7 3
4 8
7 8
8 5
4 3
8 1
1 2
2 1
6 5
7 2
7 1
6 1
3 6
6 1
6 1
7 1
7 3
2 3
3 7
4 7
8 5
3 1
2 7
2 3
4 5
3 2
4 6
4 8
4 6
8 1
1 2
8 6
5 6
7 2
6 7
5 8
4 2
6 3
6 3
8 3
6 7
8 7
8 2
6 8
1 4
5 1
2 3
4 6
7 5
8 4...

output:

result:

ok 200000 numbers

Test #9:

score: 0

Accepted

time: 27ms

memory: 3360kb

input:

9 200000
4 3 8 9 2 1 7 5 6
9 6
1 6
4 1
7 3
7 9
5 8
6 2
1 4
2 3
3 8
5 8
7 4
6 4
3 7
9 8
3 8
9 5
9 3
6 3
7 8
1 6
1 9
2 3
7 6
9 1
9 5
1 6
9 7
6 7
3 5
6 7
5 7
7 6
2 6
2 6
8 4
2 8
3 9
5 8
3 9
6 2
6 9
8 5
2 5
6 5
8 5
6 2
1 5
7 6
6 9
2 8
6 9
2 5
8 9
6 8
2 5
1 7
3 2
9 1
6 7
8 9
3 7
5 3
4 7
7 2
8 2
2 3
8 2
6...

output:

result:

ok 200000 numbers

Test #10:

score: 0

Accepted

time: 26ms

memory: 3476kb

input:

10 200000
7 10 4 9 1 6 2 3 5 8
4 9
8 7
2 3
6 10
4 5
7 6
5 6
2 6
10 1
7 5
9 10
8 9
6 9
8 5
2 3
5 1
5 7
5 4
1 9
7 4
2 7
8 6
3 10
1 2
4 1
1 5
5 8
5 7
10 3
2 7
1 5
8 10
10 6
8 10
10 4
1 10
5 4
5 10
2 10
6 5
8 6
8 1
8 9
2 4
4 2
10 9
9 8
2 8
4 1
7 10
9 7
10 9
7 3
2 6
4 8
5 9
6 9
1 2
1 5
10 6
1 2
5 10
10 7...

output:

result:

ok 200000 numbers

Test #11:

score: 0

Accepted

time: 42ms

memory: 3404kb

input:

1000 200000
82 684 685 362 991 147 175 795 885 927 938 576 958 210 494 72 823 989 662 585 461 853 955 282 310 348 861 735 249 988 994 923 513 153 496 598 776 273 965 587 833 157 244 722 30 102 935 571 432 488 211 624 121 302 867 57 588 106 901 393 394 626 363 70 887 331 870 83 708 891 46 275 193 702...

output:

result:

ok 200000 numbers

Test #12:

score: 0

Accepted

time: 19ms

memory: 3504kb

input:

1000 200000
828 824 777 731 21 589 502 672 335 762 265 349 612 24 17 713 753 324 751 69 827 579 505 469 495 846 245 382 439 415 741 169 30 347 199 730 422 742 810 97 645 253 1 372 926 865 852 629 215 2 187 340 791 362 554 802 452 685 866 370 584 592 19 100 522 350 847 702 473 33 927 102 430 296 755 ...

output:

result:

ok 200000 numbers

Test #13:

score: 0

Accepted

time: 29ms

memory: 3364kb

input:

1000 200000
246 350 704 1 73 614 451 260 652 511 954 926 565 673 697 366 736 457 802 548 106 122 488 588 31 628 700 444 118 127 196 844 346 38 512 455 193 781 237 923 572 792 74 796 828 345 57 927 754 941 456 869 544 286 272 764 689 631 416 292 702 774 807 962 192 321 806 984 490 951 330 812 406 49 ...

output:

result:

ok 200000 numbers

Test #14:

score: 0

Accepted

time: 32ms

memory: 3352kb

input:

1000 200000
858 424 321 709 582 405 422 646 542 18 17 972 681 365 13 376 735 236 848 522 404 569 540 66 245 228 73 721 765 918 108 977 814 258 436 817 216 359 929 67 179 387 901 949 344 793 902 733 923 68 44 518 626 76 830 99 890 759 107 669 498 134 914 366 724 620 935 202 83 226 196 909 195 570 296...

output:

result:

ok 200000 numbers

Test #15:

score: 0

Accepted

time: 41ms

memory: 3312kb

input:

1000 200000
195 622 863 16 431 576 39 212 950 47 185 490 855 277 272 433 671 854 793 636 226 705 547 773 351 420 681 778 954 15 980 971 270 996 489 795 509 590 789 167 545 199 343 13 700 285 561 400 599 626 784 600 846 313 326 382 514 556 359 213 273 215 562 619 573 191 744 815 148 464 575 959 817 9...

output:

result:

ok 200000 numbers

Test #16:

score: 0

Accepted

time: 55ms

memory: 4364kb

input:

199996 200000
142439 6835 18647 10242 170937 20354 144943 61038 57125 89735 195172 22802 90217 55548 45439 127625 52155 83241 13384 134236 32205 51771 34625 98189 59018 59754 7880 50600 97440 93923 3492 101571 186824 125577 159112 189850 15297 167985 173819 40737 35629 39568 167531 116850 10667 1723...

output:

result:

ok 200000 numbers

Test #17:

score: 0

Accepted

time: 58ms

memory: 4328kb

input:

199997 200000
25445 29852 42696 12166 148862 146256 1930 198693 47883 92415 146341 143134 757 92277 168845 5169 128207 168822 13682 25529 127252 178354 183014 30890 69141 61672 42121 121969 25566 181591 41752 45068 114289 195664 195472 15464 60414 77855 9289 11561 178229 85964 96333 189294 168527 93...

output:

result:

ok 200000 numbers

Test #18:

score: 0

Accepted

time: 67ms

memory: 4480kb

input:

199998 200000
80498 13704 73994 183269 56215 50077 100494 82715 180063 122020 2411 198087 47056 19993 123317 108435 185774 88038 13507 193332 11350 197929 24099 11536 52706 40264 22153 131590 104022 45671 183009 156234 138541 45256 115656 139205 60086 12997 128184 120505 8826 103001 125620 159553 62...

output:

result:

ok 200000 numbers

Test #19:

score: 0

Accepted

time: 61ms

memory: 4332kb

input:

199999 200000
97839 16933 179035 116525 195664 197736 70621 71503 4939 198510 179606 54696 80778 48486 23441 110626 196827 124446 32537 175525 98294 133241 24517 4029 127524 190403 187111 45830 10414 43203 150036 99202 133856 93446 87323 4180 3169 155750 108629 126408 58309 134869 120109 101847 8702...

output:

result:

ok 200000 numbers

Test #20:

score: 0

Accepted

time: 49ms

memory: 4472kb

input:

200000 200000
148751 122775 166403 50359 136016 141561 178365 32573 135393 176137 146238 194135 119389 91101 197518 137753 20067 50308 97900 9284 158130 163540 74091 16489 28049 21774 164793 38473 20782 6813 192733 180117 96592 67087 27908 17403 2596 169966 7533 129730 7143 185980 67694 130252 16465...

output:

result:

ok 200000 numbers

Test #21:

score: 0

Accepted

time: 41ms

memory: 3512kb

input:

1000 200000
624 13 207 250 643 149 520 558 462 56 74 387 125 430 323 841 669 442 665 449 483 90 349 852 197 102 946 685 846 19 840 205 315 824 38 812 927 126 461 378 715 473 233 979 474 866 987 863 560 545 957 389 948 593 374 72 515 253 731 183 453 5 92 503 726 574 990 127 571 327 686 236 723 842 60...

output:

result:

ok 200000 numbers

Test #22:

score: 0

Accepted

time: 37ms

memory: 3508kb

input:

1001 200000
107 973 694 589 224 604 634 732 709 983 906 852 730 672 137 363 593 554 967 500 206 269 132 821 592 866 574 469 825 767 680 257 491 148 93 948 186 402 862 338 217 351 623 774 236 296 582 305 832 393 828 513 669 836 326 139 213 170 797 786 404 882 778 693 921 706 690 369 751 325 130 504 1...

output:

result:

ok 200000 numbers

Test #23:

score: 0

Accepted

time: 34ms

memory: 3312kb

input:

1002 200000
931 489 123 687 714 254 512 833 593 1000 545 290 598 279 282 964 11 948 365 392 1002 247 729 728 941 550 375 623 673 270 949 629 955 665 487 218 856 932 154 92 20 883 105 438 464 45 346 444 831 682 304 241 117 493 91 790 953 927 703 82 742 589 295 622 910 735 674 867 792 388 688 379 478 ...

output:

result:

ok 200000 numbers

Test #24:

score: 0

Accepted

time: 34ms

memory: 3360kb

input:

1003 200000
948 99 135 829 517 804 720 118 452 789 587 430 530 623 685 43 493 934 217 76 958 29 847 311 340 172 645 134 321 3 109 161 580 2 261 241 150 774 399 965 806 476 579 869 130 396 38 322 512 188 314 943 1001 65 79 961 755 870 117 201 803 737 187 964 132 595 631 582 93 56 776 451 378 824 267 ...

output:

result:

ok 200000 numbers

Test #25:

score: 0

Accepted

time: 35ms

memory: 3308kb

input:

1004 200000
167 67 101 891 369 27 682 684 661 215 428 357 389 505 717 69 294 601 573 987 104 663 264 930 675 325 426 291 538 303 454 999 44 442 498 95 423 933 455 838 814 189 831 809 433 734 607 841 665 938 723 662 474 253 211 230 882 205 635 773 48 761 976 518 400 209 172 673 569 181 494 606 696 37...

output:

result:

ok 200000 numbers

Test #26:

score: 0

Accepted

time: 36ms

memory: 3420kb

input:

1005 200000
318 754 324 362 37 463 892 448 352 312 555 844 709 307 264 694 856 430 722 433 29 810 947 520 951 566 611 387 334 893 43 451 964 585 279 156 271 697 311 209 799 541 47 145 118 243 9 34 185 418 863 32 485 60 883 459 932 793 356 1000 601 618 351 532 967 98 134 719 995 163 915 256 765 674 3...

output:

result:

ok 200000 numbers

Test #27:

score: 0

Accepted

time: 41ms

memory: 3448kb

input:

1006 200000
78 211 559 648 747 24 457 810 659 811 231 255 77 479 139 347 679 72 111 149 195 529 683 830 158 867 880 724 813 971 563 453 485 290 627 367 801 549 774 789 508 705 461 484 270 517 589 133 539 458 701 253 656 514 213 904 140 872 126 753 533 1001 851 492 475 128 626 159 192 37 452 262 344 ...

output:

result:

ok 200000 numbers

Test #28:

score: 0

Accepted

time: 35ms

memory: 3452kb

input:

1007 200000
581 985 173 230 995 890 971 184 602 223 407 309 585 54 1 615 616 145 377 409 775 51 134 258 244 703 164 738 397 80 222 789 195 125 771 2 20 381 898 292 317 557 507 537 368 612 19 30 599 715 140 833 672 210 55 104 905 620 265 994 446 972 119 235 332 667 911 625 674 437 726 111 780 996 456...

output:

result:

ok 200000 numbers

Test #29:

score: 0

Accepted

time: 43ms

memory: 3308kb

input:

1008 200000
951 584 361 94 17 520 89 145 620 113 201 82 1007 234 293 430 467 757 767 926 161 737 337 739 985 525 962 907 974 597 37 198 544 869 983 600 632 317 209 680 204 789 407 781 195 24 853 436 964 712 958 270 721 399 668 621 279 643 405 307 160 479 965 261 283 846 585 532 165 184 350 978 517 4...

output:

result:

ok 200000 numbers

Test #30:

score: 0

Accepted

time: 36ms

memory: 3372kb

input:

1009 200000
618 822 328 413 454 309 864 882 708 993 446 889 837 222 448 617 794 955 189 102 681 669 401 756 492 569 676 181 536 591 951 798 304 192 823 571 857 428 866 188 909 235 1008 977 23 624 985 807 282 553 489 789 436 829 612 929 642 465 661 457 637 814 698 684 674 541 828 136 899 603 530 494 ...

output:

result:

ok 200000 numbers

Test #31:

score: 0

Accepted

time: 34ms

memory: 3508kb

input:

1010 200000
662 383 941 461 59 44 507 124 553 493 373 992 62 584 328 762 875 1007 73 291 37 766 6 215 138 152 105 345 844 274 432 110 532 997 248 601 66 201 923 92 839 841 747 690 163 443 639 527 95 885 801 957 393 145 455 296 65 617 384 290 720 394 735 741 346 717 181 267 284 424 228 631 917 150 23...

output:

result:

ok 200000 numbers

Test #32:

score: 0

Accepted

time: 93ms

memory: 4476kb

input:

199991 200000
125529 155034 76510 196599 89771 61282 137466 14507 17264 134977 94304 78577 45481 33875 856 71848 39554 136550 97927 84967 13628 60778 77283 167298 166926 54675 62235 82383 26122 99257 149435 172424 156761 151172 12810 116869 130258 40212 191962 115492 162295 436 135477 89946 157741 1...

output:

result:

ok 200000 numbers

Test #33:

score: 0

Accepted

time: 50ms

memory: 4368kb

input:

199992 200000
94648 142027 28101 27702 148452 67088 24671 197730 80410 137189 137066 176491 96564 94113 44632 181468 44738 96509 131999 60869 185803 71894 138752 101920 24522 172625 77233 114227 1930 147794 111400 113709 160853 170500 77421 92723 57207 189371 678 23081 47055 67741 160675 172814 1936...

output:

result:

ok 200000 numbers

Test #34:

score: 0

Accepted

time: 97ms

memory: 4304kb

input:

199993 200000
153142 9380 2190 151480 22569 148474 43837 145487 196124 120867 90200 146037 20966 114953 32500 132811 27305 124768 132131 198179 151066 80792 186462 109892 68891 152854 196912 134601 9865 150015 148336 129782 171952 91944 119872 127581 89336 59990 81236 92020 117030 188498 45528 19586...

output:

result:

ok 200000 numbers

Test #35:

score: 0

Accepted

time: 60ms

memory: 4428kb

input:

199994 200000
78337 187276 144394 16569 124843 111393 196382 37760 174538 43221 68376 84890 90800 61812 196966 36027 47780 185276 108068 63450 198444 194810 152383 161613 35115 72734 161104 100600 190056 183052 179376 17522 136711 99914 182151 85575 32999 62990 78858 97439 152456 49590 64430 119945 ...

output:

result:

ok 200000 numbers

Test #36:

score: 0

Accepted

time: 41ms

memory: 4316kb

input:

199995 200000
142381 123302 19452 73443 139579 127474 168442 164770 58324 107233 109005 51935 196601 137409 51084 3466 144749 140181 132715 63884 21630 145256 145072 74745 197524 32132 17073 92711 119982 4226 112176 143926 5852 152384 120665 4828 184039 75941 109199 199538 169692 59830 82347 124440 ...

output:

result:

ok 200000 numbers

Test #37:

score: 0

Accepted

time: 62ms

memory: 4320kb

input:

199996 200000
142439 6835 18647 10242 170937 20354 144943 61038 57125 89735 195172 22802 90217 55548 45439 127625 52155 83241 13384 134236 32205 51771 34625 98189 59018 59754 7880 50600 97440 93923 3492 101571 186824 125577 159112 189850 15297 167985 173819 40737 35629 39568 167531 116850 10667 1723...

output:

result:

ok 200000 numbers

Test #38:

score: 0

Accepted

time: 75ms

memory: 4480kb

input:

199997 200000
25445 29852 42696 12166 148862 146256 1930 198693 47883 92415 146341 143134 757 92277 168845 5169 128207 168822 13682 25529 127252 178354 183014 30890 69141 61672 42121 121969 25566 181591 41752 45068 114289 195664 195472 15464 60414 77855 9289 11561 178229 85964 96333 189294 168527 93...

output:

result:

ok 200000 numbers

Test #39:

score: 0

Accepted

time: 64ms

memory: 4320kb

input:

199998 200000
80498 13704 73994 183269 56215 50077 100494 82715 180063 122020 2411 198087 47056 19993 123317 108435 185774 88038 13507 193332 11350 197929 24099 11536 52706 40264 22153 131590 104022 45671 183009 156234 138541 45256 115656 139205 60086 12997 128184 120505 8826 103001 125620 159553 62...

output:

result:

ok 200000 numbers

Test #40:

score: 0

Accepted

time: 61ms

memory: 4476kb

input:

199999 200000
97839 16933 179035 116525 195664 197736 70621 71503 4939 198510 179606 54696 80778 48486 23441 110626 196827 124446 32537 175525 98294 133241 24517 4029 127524 190403 187111 45830 10414 43203 150036 99202 133856 93446 87323 4180 3169 155750 108629 126408 58309 134869 120109 101847 8702...

output:

result:

ok 200000 numbers

Test #41:

score: 0

Accepted

time: 59ms

memory: 4384kb

input:

200000 200000
148751 122775 166403 50359 136016 141561 178365 32573 135393 176137 146238 194135 119389 91101 197518 137753 20067 50308 97900 9284 158130 163540 74091 16489 28049 21774 164793 38473 20782 6813 192733 180117 96592 67087 27908 17403 2596 169966 7533 129730 7143 185980 67694 130252 16465...

output:

result:

ok 200000 numbers