QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#50169	#4800. Oscar's Round Must Have a Constructive Problem	bvd^#	AC ✓	248ms	11796kb	C++	1.1kb	2022-09-25 01:23:35	2022-09-25 01:23:36

Judging History

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

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

[2022-09-25 01:23:36]
评测

测评结果：AC
用时：248ms
内存：11796kb

查看

[2022-09-25 01:23:35]
提交

answer

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define sz(x) (int) (x).size()
const int maxn = 100000;
int n;
int a[maxn];
vector<int> cnt[maxn+1];
vector<int> not_appear;
vector<int> single;
int b[maxn];
void solve() {
	cin >> n; 
	
	rep(i,1,n+1) cnt[i].clear();
	not_appear.clear();
	single.clear();
	
	for (int i=0; i<n; ++i) {
		cin >> a[i];
		cnt[a[i]].push_back(i);
	}
	
	rep(i,1,n+1) if (sz(cnt[i]) == 0) not_appear.push_back(i);
	else single.push_back(i);
	
	if (sz(single) == 1) {
		cout << "NO\n";
		return;
	}
	
	int ptr = 1;
	for (auto u: not_appear) {
		int p = -1;
		while (ptr<=n) {
			if (sz(cnt[ptr]) > 1) {
				p = cnt[ptr].back(); cnt[ptr].pop_back();
				break;
			} else ptr++;
		}
		b[p] = u;
	}
	rep(i,0,sz(single)) {
		int r = single[(i+1)%sz(single)];
		b[cnt[r][0]] = single[i];
	}
	
	cout << "YES\n";
	rep(i,0,n) cout << b[i] << ' ';
	cout << '\n';
}
	
int main() {
	ios_base::sync_with_stdio(0);
	int t; cin >> t;
	rep(i,0,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: 2ms

memory: 5988kb

input:

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

output:

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

result:

ok ok

Test #2:

score: 0

Accepted

time: 229ms

memory: 5944kb

input:

output:

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

result:

ok ok

Test #3:

score: 0

Accepted

time: 248ms

memory: 5924kb

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

memory: 5928kb

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
6 10 9 8 7 3 5 4 2 1 
YES
5 4 10 9 8 7 6 3 2 1 
YES
1 10 9 7 6 5 4 8 3 2 
YES
2 10 9 8 7 5 4 3 1 6 
YES
5 10 9 4 8 7 6 3 2 1 
YES
10 4 6 3 2 5 9 1 7 8 
YES
7 8 9 4 10 3 2 6 5 1 
NO
YES
1 5 3 4 9 8 7 6 2 10 
YES
1 10 9 8 7 4 6 5 3 2 
YES
6 7 4 3 5 10 2 9 1 8 
NO
NO
YES
6 10 8 3 7 9 5 2 4 1 
YES
6...

result:

ok ok

Test #5:

score: 0

Accepted

time: 74ms

memory: 5984kb

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

result:

ok ok

Test #6:

score: 0

Accepted

time: 40ms

memory: 7604kb

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
657 1000 999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 970 969 968 967 966 965 964 963 962 961 960 959 958 957 956 955 954 953 952 951 950 949 948 947 946 945 944 943 942 941 940 939 938 937 936 935 934 933 932 931 93...

result:

ok ok

Test #7:

score: 0

Accepted

time: 57ms

memory: 8656kb

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
1755 10000 9999 9998 9997 9996 9995 9994 9993 9992 9991 9990 9989 9988 9987 9986 9985 9984 9983 9982 9981 9980 9979 9978 9977 9976 9975 9974 9973 9972 9971 9970 9969 9968 9967 9966 9965 9964 9963 9962 9961 9960 9959 9958 9957 9956 9955 9954 9953 9952 9951 9950 9949 9948 9947 9946 9945 9944 9943 ...

result:

ok ok

Test #8:

score: 0

Accepted

time: 54ms

memory: 8888kb

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
15657 25000 24999 24998 24997 24996 24995 24994 24993 24992 24991 24990 24989 24988 24987 24986 24985 24984 24983 24982 24981 24980 24979 24978 24977 24976 24975 24974 24973 24972 24971 24970 24969 24968 24967 24966 24965 24964 24963 24962 24961 24960 24959 24958 24957 24956 24955 24954 24953 24...

result:

ok ok

Test #9:

score: 0

Accepted

time: 64ms

memory: 9888kb

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
31708 22702 9333 35776 21483 28631 35775 35774 8079 28630 35773 35050 21482 35772 28629 28628 21481 21480 28627 50000 14314 14313 46864 28626 21479 14312 7137 35771 28625 21478 49999 35770 14311 49998 14310 32825 28624 7136 49997 14309 35769 7135 21477 28623 21476 7134 49996 35768 7133 42913 143...

result:

ok ok

Test #10:

score: 0

Accepted

time: 63ms

memory: 11796kb

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
92905 49999 49998 49997 25575 100000 49996 99999 49995 99998 49994 49993 49992 99997 99996 99995 49991 99994 49990 49989 49988 49987 99993 99992 99991 99990 49986 49985 49984 99989 99988 49983 49982 99987 49981 99986 49980 99985 99984 49979 99983 99982 49978 99981 49977 49976 99980 99979 49975 4...

result:

ok ok