QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#434538	#4800. Oscar's Round Must Have a Constructive Problem	ship2077	AC ✓	1221ms	4656kb	C++14	822b	2024-06-08 16:30:39	2024-06-08 16:30:42

Judging History

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

[2024-06-08 16:30:42]
评测

测评结果：AC
用时：1221ms
内存：4656kb

查看

[2024-06-08 16:30:39]
提交

answer

#include<bits/stdc++.h>
using namespace std;
mt19937 mt(time(NULL));
constexpr int M=1e5+5;
int n,cnt,num,p[M],per[M];
int read(){
	int x=0;char ch=getchar();
	while (!isdigit(ch)) ch=getchar();
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x;
}
int rnd(int l,int r){return mt()%(r-l+1)+l;}
void solve(){ n=read();num=0;
	for (int i=1;i<=n;i++) p[i]=read();
	for (int i=1;i<=n;i++) num+=p[i]==p[1];
	if (num==n) return puts("NO"),void();
	iota(per+1,per+n+1,1);
	cnt=0;while (1){ bool flag=0;
		for (int i=1;i<n;i++)
			if (per[i]==p[i]) flag=1,
				swap(per[i],per[rnd(i+1,n)]);
		if (per[n]==p[n]) swap(per[n],per[1]),flag=1;
		cnt++; if (!flag) break;
	} puts("YES");
	for (int i=1;i<=n;i++) printf("%d%c",per[i]," \n"[i==n]);
}
int main(){int T=read();while (T--) solve();return 0;}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 4024kb

input:

3
3
3 3 3
3
3 2 1
6
1 1 4 5 1 4

output:

NO
YES
1 3 2
YES
3 2 1 4 5 6

result:

ok ok

Test #2:

score: 0

Accepted

time: 19ms

memory: 3892kb

input:

output:

NO
NO
YES
2 1
YES
1 2
NO
NO
YES
3 2 1
YES
3 2 1
YES
2 1 3
YES
2 1 3
YES
3 1 2
YES
2 1 3
YES
2 1 3
YES
3 1 2
YES
1 2 3
YES
1 2 3
YES
3 2 1
YES
1 3 2
NO
YES
1 3 2
YES
1 2 3
YES
1 2 3
YES
3 2 1
YES
1 2 3
YES
1 2 3
YES
2 3 1
YES
1 3 2
YES
2 3 1
YES
1 3 2
YES
1 2 3
YES
1 2 3
NO
NO
YES
3 2 4 1
YES
4 2 3 1...

result:

ok ok

Test #3:

score: 0

Accepted

time: 3ms

memory: 3760kb

input:

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok ok

Test #4:

score: 0

Accepted

time: 25ms

memory: 3804kb

input:

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

output:

YES
1 2 10 4 5 3 7 8 9 6
YES
5 2 3 4 7 6 10 8 9 1
YES
1 2 3 4 5 6 7 8 9 10
YES
1 2 3 4 5 7 10 8 9 6
YES
1 2 3 4 5 6 7 8 9 10
YES
10 2 3 6 5 4 7 8 9 1
YES
1 2 3 4 5 6 7 8 9 10
NO
YES
1 2 3 4 5 6 7 8 9 10
YES
7 1 9 6 5 4 10 8 3 2
YES
1 2 3 4 5 7 6 8 9 10
NO
NO
YES
1 2 3 4 5 6 7 8 10 9
YES
1 2 9 4 5 6 ...

result:

ok ok

Test #5:

score: 0

Accepted

time: 32ms

memory: 3964kb

input:

5000
100
37 37 37 58 58 58 58 58 58 58 37 58 37 37 37 58 37 37 37 37 58 58 37 37 37 37 58 37 58 58 58 58 37 58 58 58 37 58 37 37 37 37 58 37 37 37 58 37 37 58 37 37 37 58 37 37 58 37 58 58 58 58 37 37 58 58 58 37 37 58 58 37 37 58 37 58 58 37 58 58 58 37 58 58 37 58 58 58 37 58 58 58 37 58 58 37 58 ...

output:

YES
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 58 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 90 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 37 91 92 93 94 95 96 97 98 99 100
YES
...

result:

ok ok

Test #6:

score: 0

Accepted

time: 58ms

memory: 3904kb

input:

500
1000
452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452 452...

output:

NO
NO
NO
YES
171 2 661 232 195 6 7 8 612 10 867 621 13 14 15 16 17 18 38 323 21 474 81 24 25 118 821 28 374 30 31 32 705 918 35 580 308 829 39 40 639 687 43 44 340 46 716 48 49 354 51 52 53 311 55 56 393 433 59 582 61 349 63 64 65 559 12 197 69 70 71 842 316 74 75 857 77 558 334 80 944 111 258 84 95...

result:

ok ok

Test #7:

score: 0

Accepted

time: 122ms

memory: 3924kb

input:

50
10000
9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9931 9...

output:

YES
5161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3580 19 20 21 22 23 24 25 26 27 9869 29 30 31 32 33 34 35 36 37 38 39 40 41 42 4665 44 45 46 47 9702 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 8786 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

result:

ok ok

Test #8:

score: 0

Accepted

time: 639ms

memory: 4056kb

input:

20
25000
2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2181 2...

output:

YES
4339 2 3 4 5 6 7 20399 9 10 11 12 13 7012 15 16 17 18 20796 20 21 22 22751 24 25 26 27 28 29 30 31 32 33 34 1520 36 37 15739 12113 40 7659 42 43 44 45 46 15698 48 49 50 51 429 53 54 20081 19076 57 15710 59 60 61 62 63 64 65 14493 67 68 69 14332 71 23601 5111 74 75 76 13695 78 79 80 81 82 83 1910...

result:

ok ok

Test #9:

score: 0

Accepted

time: 1221ms

memory: 4356kb

input:

10
50000
32825 31708 22702 32825 22702 31708 32825 32825 9333 31708 32825 46864 22702 32825 31708 31708 22702 22702 31708 46864 9333 9333 1785 31708 22702 9333 1785 32825 31708 22702 46864 32825 9333 46864 9333 35050 31708 1785 46864 9333 32825 1785 22702 31708 22702 1785 46864 32825 1785 35050 9333...

output:

YES
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 101 ...

result:

ok ok

Test #10:

score: 0

Accepted

time: 20ms

memory: 4656kb

input:

5
100000
25575 25575 25575 25575 38740 38740 25575 38740 25575 38740 25575 25575 25575 38740 38740 38740 25575 38740 25575 25575 25575 25575 38740 38740 38740 38740 25575 25575 25575 38740 38740 25575 25575 38740 25575 38740 25575 38740 38740 25575 38740 38740 25575 38740 25575 25575 38740 38740 255...

output:

YES
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 101 ...

result:

ok ok