QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#658445	#2789. Sorting	Pioneer^#	36	15ms	4188kb	C++20	1.1kb	2024-10-19 16:49:51	2024-10-19 16:49:55

Judging History

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

[2024-10-19 16:49:55]
评测

测评结果：36
用时：15ms
内存：4188kb

查看

[2024-10-19 16:49:51]
提交

answer

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

using namespace std;

const int MAX=100000;

int n,m,x[MAX],y[MAX];
int s[MAX];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n=N,m=M;
	for(int i=0;i<M;i++)x[i]=X[i],y[i]=Y[i];
	for(int i=0;i<N;i++)s[i]=S[i];
    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;
	for(int i=0;i<m;i++){
		swap(v[x[i]],v[y[i]]);
		vector<int> tov=need;
		for(int j=i+1;j<m;j++){
			swap(tov[x[j]],tov[y[j]]);
		}
		bool ok=0;
		for(int k=0;k<n;k++){
			if(tov[k]!=v[k]){
				for(int j=0;j<n;j++){
					if(tov[j]==v[k]){
						ok=1;
						swaps.push_back({k,j});
						swap(v[k],v[j]);
						break;
					}
				}
				if(ok)break;
			}
		}
		// tov=need;
		// for(int j=i+1;j<m;j++){
		// 	swap(tov[x[j]],tov[y[j]]);
		// }
		// for(int i=0;i<n;i++)cout<<tov[i]<<" "<<v[i]<<"\n";
		// cout<<"\n";
		if(!ok)swaps.push_back({0,0});
	}
	// cout<<"\n";
	assert(v==need);
	for(int i=0;i<m;i++){
		P[i]=swaps[i].first;
		Q[i]=swaps[i].second;
	}
	return M;
}

源文件, 语言: C++20

详细

Subtask #1:

score: 8

Accepted

Test #1:

score: 8

Accepted

time: 0ms

memory: 3644kb

input:

output:

1
0 0

result:

ok correct

Test #2:

score: 8

Accepted

time: 0ms

memory: 3692kb

input:

output:

result:

ok correct

Test #3:

score: 8

Accepted

time: 0ms

memory: 3716kb

input:

output:

result:

ok correct

Test #4:

score: 8

Accepted

time: 0ms

memory: 3680kb

input:

output:

result:

ok correct

Test #5:

score: 8

Accepted

time: 0ms

memory: 3676kb

input:

output:

result:

ok correct

Test #6:

score: 8

Accepted

time: 0ms

memory: 3672kb

input:

output:

result:

ok correct

Test #7:

score: 8

Accepted

time: 0ms

memory: 3788kb

input:

output:

result:

ok correct

Subtask #2:

score: 12

Accepted

Test #8:

score: 12

Accepted

time: 0ms

memory: 3684kb

input:

output:

result:

ok correct

Test #9:

score: 12

Accepted

time: 0ms

memory: 3744kb

input:

output:

result:

ok correct

Test #10:

score: 12

Accepted

time: 7ms

memory: 3900kb

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: 2ms

memory: 4064kb

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

memory: 3912kb

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: 3916kb

input:

output:

result:

ok correct

Test #14:

score: 16

Accepted

time: 0ms

memory: 3800kb

input:

output:

result:

ok correct

Test #15:

score: 16

Accepted

time: 6ms

memory: 3868kb

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: 6ms

memory: 3808kb

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: 6ms

memory: 3816kb

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: 4036kb

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: 3692kb

input:

output:

result:

ok correct

Test #20:

score: 18

Accepted

time: 0ms

memory: 3680kb

input:

output:

result:

ok correct

Test #21:

score: 0

Runtime Error

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:

Unauthorized output

result:

Subtask #5:

score: 0

Runtime Error

Test #28:

score: 20

Accepted

time: 14ms

memory: 4188kb

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: 15ms

memory: 3948kb

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

Runtime Error

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:

Unauthorized output