QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#63742#4800. Oscar's Round Must Have a Constructive Problemneko_nyaaAC ✓166ms9320kbC++231.1kb2022-11-23 11:51:172022-11-23 11:51:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-23 11:51:26]
  • 评测
  • 测评结果：AC
  • 用时：166ms
  • 内存：9320kb
查看
  • [2022-11-23 11:51:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
	int n; cin >> n;
	vector<int> p(n); map<int, int> cnt;
	for (int i = 0; i < n; i++) {
		cin >> p[i]; cnt[p[i]]++;
		if (cnt[p[i]] == n) {
			cout << "NO\n";
			return;
		}
	}

	int mx = 0;
	for (int i = 1; i <= n; i++) {
		if (cnt[i] > cnt[mx]) mx = i;
	}

	vector<int> ans(n);
	for (int i = 0; i < n; i++) {
		ans[i] = i+1;
	}

	vector<int> p1;
	for (int i = 0; i < n; i++) {
		if (p[i] != mx) p1.push_back(i);
	}

	while (1) {
		random_shuffle(ans.begin(), ans.end());
		int pos1, pos2;
		for (int i = 0; i < n; i++) {
			if (ans[i] == mx) pos2 = i;
		}
		pos1 = p1[0];
		swap(ans[pos1], ans[pos2]);

		bool ok = 1;
		for (int i = 0; i < n; i++) {
			if (p[i] == ans[i]) {
				ok = 0; break;
			}
		}

		if (ok) {
			cout << "YES\n";
			for (int i: ans) cout << i << ' ';
				cout << '\n';
			return;
		}
	}
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int t; cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3300kb

input:

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

output:

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

result:

ok ok

Test #2:

score: 0
Accepted
time: 72ms
memory: 3300kb

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
2 3 1 
YES
2 3 1 
YES
3 1 2 
YES
2 3 1 
YES
3 1 2 
YES
3 1 2 
YES
2 1 3 
YES
3 2 1 
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
1 2 3 
YES
3 2 1 
YES
1 2 3 
YES
1 2 3 
YES
1 3 2 
YES
1 3 2 
YES
2 1 3 
YES
2 3 1 
YES
1 2 3 
YES
2 1 3 
NO
...

result:

ok ok

Test #3:

score: 0
Accepted
time: 18ms
memory: 3296kb

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: 99ms
memory: 3340kb

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

result:

ok ok

Test #5:

score: 0
Accepted
time: 90ms
memory: 3296kb

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

result:

ok ok

Test #6:

score: 0
Accepted
time: 104ms
memory: 3500kb

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
111 291 702 70 561 469 707 897 165 927 796 323 362 3 568 793 603 930 644 721 590 827 421 579 364 193 552 853 972 924 353 913 544 586 397 115 640 716 202 281 67 673 933 952 880 177 107 799 883 271 724 166 751 44 392 203 50 106 911 319 388 390 142 409 487 741 718 34 558 703 26 782 711 966...

result:

ok ok

Test #7:

score: 0
Accepted
time: 114ms
memory: 3940kb

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
3187 1191 3594 7551 2401 469 707 3755 165 7917 3880 4336 362 6188 8963 3338 1417 8662 5057 7791 7992 7389 421 2319 5982 1983 3141 1688 4474 8429 7008 5179 6059 2256 8763 3672 7339 9955 3054 6931 67 673 3269 4494 9842 6538 5152 5135 3901 271 1269 1312 4765 6571 8402 8167 1387 6475 7016 9031 5664 ...

result:

ok ok

Test #8:

score: 0
Accepted
time: 128ms
memory: 4832kb

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
16526 1191 3594 7551 17577 20239 18449 19823 165 7917 3880 21525 362 6188 8963 11770 1417 8662 19924 16383 7992 7389 23696 2319 13081 1983 3141 21846 10006 19717 7008 12446 19133 2256 18105 3672 12386 23208 3054 21678 67 15070 3269 12871 13160 13369 22029 5135 3901 271 1269 1312 13179 10321 8402...

result:

ok ok

Test #9:

score: 0
Accepted
time: 166ms
memory: 6420kb

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
9333 2884 25886 26207 42728 43753 12370 24138 18545 6426 44069 27808 3150 29361 27043 10080 22483 4113 18944 23761 46787 29890 48750 6723 34142 19711 24829 265 5349 145 39169 30315 45785 3155 39625 43743 41490 6502 27075 35309 7124 45282 19785 44827 40559 23183 19321 17431 18290 43191 17557 1351...

result:

ok ok

Test #10:

score: 0
Accepted
time: 161ms
memory: 9320kb

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
38740 25720 84658 90057 99607 50202 18449 66784 27116 32648 49102 49766 362 83161 26936 69299 89390 53329 19924 16383 73600 7389 23696 2319 49849 1983 73838 21846 48247 34820 72221 52414 32013 2256 76615 3672 99307 76134 3054 21678 38878 15070 3269 95278 47256 92095 22029 75817 97642 271 82734 1...

result:

ok ok
English 繁體中文 简体中文

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