QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#659072	#2789. Sorting	Pioneer^#	36	2ms	4324kb	C++20	1.3kb	2024-10-19 18:28:43	2024-10-19 18:28:47

Judging History

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

[2024-10-19 18:28:47]
评测

测评结果：36
用时：2ms
内存：4324kb

查看

[2024-10-19 18:28:43]
提交

answer

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX=200000;

int n,m;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n=N,m=M;
    vector<int> v(n),need(n);
	vector<pair<int,int>> swaps;
	for(int i=0;i<n;i++)v[i]=S[i],need[i]=i;
	vector<int> tov=need;
	for(int j=0;j<m;j++){
		swap(tov[X[j]],tov[Y[j]]);
	}
	vector<int> tov1(n);
	for(int i=0;i<n;i++)tov1[tov[i]]=i;
	swap(tov,tov1);
	for(int i=0;i<n;i++){
		tov1[tov[i]]=i;
	}
	set<int> st;
	for(int i=0;i<n;i++){
		if(tov[i]!=v[i])st.insert(i);
	}
	// 0 4
	// 0 4
	// 0 1
	// 2 4
	for(int i=0;i<m;i++){
		swap(v[X[i]],v[Y[i]]);
		swap(tov1[tov[X[i]]],tov1[tov[Y[i]]]);
		swap(tov[X[i]],tov[Y[i]]);
		while(!st.empty()&&tov[*st.begin()]==v[*st.begin()])st.erase(st.begin());
		if(!st.empty()){
			int k=*st.begin();
			st.erase(st.begin());
			int j=tov1[v[k]];
			swaps.push_back({k,j});
			// cout<<k<<" "<<j<<" "<<v[k]<<" "<<tov[j]<<"\n";
			swap(v[k],v[j]);
			if(tov[j]!=v[j])st.insert(j);
			if(tov[k]!=v[k])st.insert(k);
		}
		else swaps.push_back({0,0});
		// for(int j=0;j<n;j++)cout<<v[j]<<" "<<tov[j]<<"\n";
	}
	// for(int x:v)cout<<x<<" ";
	// cout<<"\n";
	assert(v==need);
	for(int i=0;i<m;i++){
		P[i]=swaps[i].first;
		Q[i]=swaps[i].second;
	}
	return M;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 8

Accepted

Test #1:

score: 8

Accepted

time: 0ms

memory: 3760kb

input:

output:

1
0 0

result:

ok correct

Test #2:

score: 8

Accepted

time: 0ms

memory: 3636kb

input:

output:

result:

ok correct

Test #3:

score: 8

Accepted

time: 0ms

memory: 3616kb

input:

output:

result:

ok correct

Test #4:

score: 8

Accepted

time: 0ms

memory: 3756kb

input:

output:

result:

ok correct

Test #5:

score: 8

Accepted

time: 0ms

memory: 4052kb

input:

output:

result:

ok correct

Test #6:

score: 8

Accepted

time: 0ms

memory: 3764kb

input:

output:

result:

ok correct

Test #7:

score: 8

Accepted

time: 0ms

memory: 3756kb

input:

output:

result:

ok correct

Subtask #2:

score: 12

Accepted

Test #8:

score: 12

Accepted

time: 0ms

memory: 3928kb

input:

output:

result:

ok correct

Test #9:

score: 12

Accepted

time: 0ms

memory: 3576kb

input:

output:

result:

ok correct

Test #10:

score: 12

Accepted

time: 0ms

memory: 4004kb

input:

98
82 70 31 12 27 51 84 90 66 8 49 52 74 91 46 7 96 67 63 85 34 50 87 83 58 78 26 39 77 48 2 55 94 25 61 56 53 13 32 86 72 20 37 73 9 93 65 28 18 11 71 59 88 35 76 40 24 36 33 3 17 29 38 5 21 15 79 30 62 92 45 80 64 95 43 75 97 23 16 57 22 60 41 69 0 42 14 10 47 68 19 4 1 6 44 81 54 89
2940
0 0
0 0
...

output:

result:

ok correct

Test #11:

score: 12

Accepted

time: 1ms

memory: 4036kb

input:

99
8 14 3 0 98 74 18 10 50 93 49 23 80 2 54 79 90 31 66 38 81 36 42 83 39 7 9 71 59 62 67 4 68 5 70 72 34 95 25 27 45 61 97 48 29 15 46 12 87 22 26 63 77 84 11 85 30 24 40 78 41 1 96 69 94 19 6 65 33 13 52 75 88 82 86 20 92 43 89 47 28 73 35 32 53 60 21 16 37 58 44 76 57 56 17 55 91 51 64
2970
0 0
0...

output:

result:

ok correct

Test #12:

score: 12

Accepted

time: 1ms

memory: 3848kb

input:

96
12 91 75 59 44 30 52 63 41 13 93 79 82 60 85 78 50 53 57 8 80 67 34 24 87 17 47 33 83 21 81 40 89 49 32 70 26 9 43 7 11 37 94 36 23 28 90 42 35 25 62 56 20 84 55 45 46 22 77 51 0 69 1 31 54 2 3 58 88 76 5 6 65 92 39 66 15 95 10 27 14 86 72 4 68 18 38 19 64 73 71 74 48 29 61 16
2880
0 0
0 0
0 0
0 ...

output:

result:

ok correct

Subtask #3:

score: 16

Accepted

Test #13:

score: 16

Accepted

time: 0ms

memory: 3628kb

input:

output:

result:

ok correct

Test #14:

score: 16

Accepted

time: 0ms

memory: 3624kb

input:

output:

result:

ok correct

Test #15:

score: 16

Accepted

time: 1ms

memory: 3732kb

input:

96
7 15 12 95 11 50 20 42 81 29 58 80 56 71 63 66 44 6 64 39 2 22 73 1 24 27 69 28 45 25 60 61 5 94 14 65 9 86 68 32 79 37 3 57 34 35 10 88 76 78 21 93 19 53 84 52 4 33 38 55 62 67 77 41 31 48 91 49 51 43 90 8 87 54 16 17 70 46 85 0 75 92 74 47 36 89 30 13 59 26 40 18 82 83 72 23
2880
0 1
0 1
0 1
0 ...

output:

result:

ok correct

Test #16:

score: 16

Accepted

time: 1ms

memory: 3844kb

input:

99
28 2 16 95 73 6 30 90 18 46 82 69 59 4 40 49 33 29 66 86 97 56 22 96 38 35 67 15 83 44 36 72 81 41 76 47 34 87 65 9 92 57 0 55 68 5 32 17 61 50 14 19 58 24 98 48 53 60 45 12 39 3 8 74 88 77 13 85 84 42 79 51 94 70 10 25 75 31 62 27 64 1 80 78 21 37 7 63 52 23 71 20 54 26 43 91 89 93 11
2970
0 1
0...

output:

result:

ok correct

Test #17:

score: 16

Accepted

time: 1ms

memory: 3808kb

input:

99
52 0 59 91 38 87 65 75 48 11 64 60 95 71 62 79 49 30 47 56 33 16 94 8 78 36 13 68 9 35 74 77 80 24 15 83 28 66 12 51 92 84 43 40 4 46 63 57 17 85 42 25 81 14 50 31 72 34 70 88 67 53 6 37 44 45 96 69 2 86 76 55 3 82 22 5 93 39 26 41 98 7 27 1 20 29 23 19 54 18 61 90 89 32 97 73 10 58 21
2970
0 1
0...

output:

result:

ok correct

Test #18:

score: 16

Accepted

time: 0ms

memory: 3904kb

input:

output:

result:

ok correct

Subtask #4:

score: 0

Runtime Error

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Test #19:

score: 18

Accepted

time: 0ms

memory: 3604kb

input:

output:

result:

ok correct

Test #20:

score: 18

Accepted

time: 0ms

memory: 3708kb

input:

output:

result:

ok correct

Test #21:

score: 18

Accepted

time: 2ms

memory: 4148kb

input:

481
264 22 307 266 238 227 68 26 13 12 384 162 410 306 374 311 442 38 407 310 280 308 333 146 326 381 367 110 190 33 141 468 153 393 157 415 229 75 276 392 349 348 179 445 317 64 78 20 323 257 292 395 129 259 165 398 151 219 14 116 338 188 243 61 150 84 72 340 155 133 459 464 248 433 124 399 177 62 ...

output:

result:

ok correct

Test #22:

score: 18

Accepted

time: 2ms

memory: 4000kb

input:

478
458 446 125 326 318 327 263 67 453 296 46 116 270 440 323 38 181 235 415 412 95 365 133 397 157 441 348 223 459 449 149 168 59 107 171 262 328 450 289 314 141 139 29 393 211 477 146 239 433 142 269 145 342 155 238 172 206 23 108 31 48 117 180 424 50 147 325 468 161 291 272 130 93 472 245 207 154...

output:

result:

ok correct

Test #23:

score: 18

Accepted

time: 0ms

memory: 4012kb

input:

496
426 495 20 100 83 50 3 247 94 52 290 45 179 160 344 239 270 133 492 398 131 476 271 436 69 351 401 494 111 76 393 432 431 207 53 350 24 288 278 359 413 253 181 166 186 336 35 173 209 448 352 364 188 434 203 38 439 32 328 285 213 112 47 128 136 303 49 180 444 132 177 114 287 475 161 483 14 108 66...

output:

result:

ok correct

Test #24:

score: 18

Accepted

time: 2ms

memory: 4092kb

input:

484
307 290 7 454 181 133 142 213 413 207 146 153 236 111 320 453 476 103 316 158 235 388 150 155 329 297 196 345 335 197 173 0 156 59 357 85 161 280 229 98 412 187 42 226 244 203 99 475 223 81 56 309 273 87 159 317 50 313 199 366 185 409 172 483 447 427 71 284 330 30 73 414 154 70 302 417 113 107 2...

output:

result:

ok correct

Test #25:

score: 0

Runtime Error

input:

496
145 300 465 228 235 186 373 183 142 208 278 11 410 286 392 245 44 470 211 368 283 240 265 120 30 68 71 158 263 356 439 243 27 311 86 134 201 33 319 371 254 181 231 89 214 435 113 59 48 151 317 143 320 195 377 426 408 303 22 47 149 330 180 175 412 140 102 204 381 441 50 258 232 105 266 52 122 423...

output:

Unauthorized output

result:

Subtask #5:

score: 0

Runtime Error

Test #28:

score: 20

Accepted

time: 1ms

memory: 4148kb

input:

1800
530 1775 466 953 230 1179 944 752 990 1316 275 1029 158 152 1673 1706 172 115 599 1661 131 699 1112 454 551 1059 291 495 28 67 773 480 839 462 1210 757 879 285 439 3 1429 820 26 1023 942 199 356 625 1705 1421 144 1529 716 7 1485 1027 1599 696 517 1353 456 1389 273 1363 1414 1177 718 41 777 1621...

output:

result:

ok correct

Test #29:

score: 20

Accepted

time: 1ms

memory: 4028kb

input:

1950
1718 335 1071 714 1080 1828 1472 410 553 1269 297 401 1021 621 1763 528 205 1231 406 5 715 876 1474 1110 653 862 838 291 1092 549 955 1334 1044 300 1070 720 1877 484 1597 1948 1078 28 87 1193 505 1024 1259 63 852 960 633 1573 713 504 15 820 1852 752 1601 1168 471 1903 499 693 1209 1492 56 908 9...

output:

result:

ok correct

Test #30:

score: 20

Accepted

time: 1ms

memory: 3868kb

input:

1853
452 1299 444 1527 510 1801 34 1178 1589 1782 342 1800 735 761 879 999 1122 1772 236 566 1459 1256 1149 1498 1827 1027 715 1377 6 306 1811 950 500 890 196 1825 1568 1157 943 1422 475 1237 1792 1796 1363 1217 889 968 1439 1116 322 795 1088 1358 1833 96 118 543 1337 207 876 1144 805 215 1433 903 1...

output:

result:

ok correct

Test #31:

score: 20

Accepted

time: 1ms

memory: 4256kb

input:

1957
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

result:

ok correct

Test #32:

score: 20

Accepted

time: 0ms

memory: 4036kb

input:

1993
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

result:

ok correct

Test #33:

score: 20

Accepted

time: 1ms

memory: 3872kb

input:

1935
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

result:

ok correct

Test #34:

score: 20

Accepted

time: 1ms

memory: 4324kb

input:

1999
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 127 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

result:

ok correct

Test #35:

score: 20

Accepted

time: 1ms

memory: 3968kb

input:

1901
952 410 986 1281 736 1411 1256 622 375 1423 718 1153 1238 643 120 1336 1097 881 1140 1395 1195 847 925 967 280 1859 966 360 815 770 634 1774 1359 1871 1589 618 991 571 1704 170 1548 1791 225 741 1561 35 1334 1632 203 894 728 1681 1849 22 1152 1719 701 1886 1037 1309 1576 993 1350 1643 893 1888 ...

output:

result:

ok correct

Test #36:

score: 20

Accepted

time: 1ms

memory: 3964kb

input:

1931
1361 1614 1425 1627 1210 1778 166 420 1747 1792 1060 1914 611 833 1280 86 1754 1194 762 185 488 1368 1794 1153 1466 1689 1185 168 1622 1582 959 197 103 1809 1586 436 633 853 463 738 820 630 159 398 150 1370 558 281 1849 483 1691 350 1867 1871 1392 1791 1697 926 639 1865 1063 1726 262 1009 495 1...

output:

result:

ok correct

Test #37:

score: 20

Accepted

time: 1ms

memory: 4020kb

input:

1938
428 1641 1051 1154 1556 814 986 237 1557 1082 84 1382 1823 1591 1779 1565 193 574 1683 1259 405 393 366 644 612 562 303 1567 997 1422 868 132 74 1508 1002 965 1752 500 1148 529 1119 1841 930 1608 1472 310 1435 261 705 908 588 1710 722 1427 1825 1256 1175 379 45 902 1861 62 729 1303 759 766 1022...

output:

result:

ok correct

Test #38:

score: 20

Accepted

time: 1ms

memory: 4036kb

input:

1997
1053 110 1738 1025 1245 1257 472 471 13 1215 1811 1371 476 1631 1028 892 1191 20 1323 868 435 1063 870 758 1538 155 1105 27 987 1345 1228 1473 452 1092 1561 1874 1417 95 252 565 1315 1389 533 1078 1259 1440 772 0 1588 1750 1451 644 659 1161 173 200 1680 1040 1827 1567 1069 12 1730 866 1493 65 5...

output:

result:

ok correct

Test #39:

score: 20

Accepted

time: 1ms

memory: 3904kb

input:

1989
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

result:

ok correct

Test #40:

score: 0

Runtime Error

input:

1961
0 1 272 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100...

output:

Unauthorized output