QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#434538#4800. Oscar's Round Must Have a Constructive Problemship2077AC ✓1221ms4656kbC++14822b2024-06-08 16:30:392024-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;}
源文件, 语言: C++14

详细

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:

50069
1
1
2
1 1
2
1 2
2
2 1
2
2 2
3
1 1 1
3
1 1 2
3
1 1 3
3
1 2 1
3
1 2 2
3
1 2 3
3
1 3 1
3
1 3 2
3
1 3 3
3
2 1 1
3
2 1 2
3
2 1 3
3
2 2 1
3
2 2 2
3
2 2 3
3
2 3 1
3
2 3 2
3
2 3 3
3
3 1 1
3
3 1 2
3
3 1 3
3
3 2 1
3
3 2 2
3
3 2 3
3
3 3 1
3
3 3 2
3
3 3 3
4
1 1 1 1
4
1 1 1 2
4
1 1 1 3
4
1 1 1 4
4
1 1 2 1
...

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:

100000
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1...

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
English 繁體中文 简体中文

服务器时间: 2024-11-30 08:55:25 | 开源项目