QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#99684 | #4800. Oscar's Round Must Have a Constructive Problem | ckiseki# | AC ✓ | 85ms | 6404kb | C++20 | 2.3kb | 2023-04-23 14:52:35 | 2023-04-23 14:52:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define orange(a...) orange_(#a, a)
#define debug(a...) debug_(#a, a)
template <typename i>
void orange_(const char * s, i l, i r) {
cerr << "\e[1;32m[ " << s << " ] = [ ";
for (int f = 0; l != r; l++)
cerr << (f++ ? " " : "") << *l;
cerr << " ]\e[0m\n";
}
template <typename ...T>
void debug_(const char * s, T ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int cnt = sizeof...(T);
(..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
int main() {
mt19937 rng(114514);
cin.tie(nullptr)->sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
--a[i];
}
bool allsame = true;
for (int i = 1; i < n; i++) {
if (a[i] != a[0])
allsame = false;
}
if (allsame) {
cout << "NO\n";
continue;
}
vector<pair<int,int>> e;
for (int i = 0; i < n; i++) {
e.emplace_back(a[i], i);
}
sort(e.begin(), e.end());
{
size_t j = 0;
for (int i = 0; i < n; i++) {
if (j == 0 || e[j-1].first != e[i].first) {
e[j++] = e[i];
}
}
e.resize(j);
}
vector<int> p(n, -1), used(n);
int m = e.size();
for (int i = 0; i < m; i++) {
auto [v1, p1] = e[i];
auto [v2, p2] = e[(i + 1) % m];
p[p1] = v2;
used[v2] = true;
}
vector<int> num, pos;
for (int i = 0; i < n; i++) {
if (!used[i]) {
num.push_back(i);
}
if (p[i] == -1) {
pos.push_back(i);
}
}
assert (num.size() == pos.size());
for (size_t i = 0; i < num.size(); i++) {
p[pos[i]] = num[i];
}
cout << "YES\n";
for (int i = 0; i < n; i++)
cout << p[i]+1 << (i+1==n ? '\n' : ' ');
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3476kb
input:
3 3 3 3 3 3 3 2 1 6 1 1 4 5 1 4
output:
NO YES 1 3 2 YES 4 2 5 1 3 6
result:
ok ok
Test #2:
score: 0
Accepted
time: 51ms
memory: 3436kb
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 3 2 1 YES 2 1 3 YES 2 1 3 YES 2 3 1 YES 3 1 2 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 3 1 2 YES 3 1 2 YES 3 2 1 YES 3 2 1 YES 1 3 2 YES 1 2 3 YES 1 3 2 YES 1 3 2 YES 2 3 1 YES 2 3 1 YES 1 2 3 YES 2 1 3 NO NO YES 2 3 4 1 YES 3 2 4 1...
result:
ok ok
Test #3:
score: 0
Accepted
time: 15ms
memory: 3356kb
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: 62ms
memory: 3488kb
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 1 2 4 5 3 7 8 9 10 YES 5 4 1 2 3 6 7 8 9 10 YES 1 2 3 4 5 6 7 8 9 10 YES 2 1 3 4 5 7 8 9 10 6 YES 5 1 2 4 3 6 7 8 9 10 YES 5 10 1 2 3 4 6 7 8 9 YES 10 4 1 7 6 2 3 8 5 9 NO YES 9 2 3 10 1 5 6 7 8 4 YES 1 2 3 5 6 4 7 8 9 10 YES 6 1 2 3 5 4 7 8 9 10 NO NO YES 3 1 2 9 4 6 5 7 8 10 YES 3 8 4 1 2 6 ...
result:
ok ok
Test #5:
score: 0
Accepted
time: 56ms
memory: 3372kb
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 1 2 37 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 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 YES ...
result:
ok ok
Test #6:
score: 0
Accepted
time: 71ms
memory: 3488kb
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 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 9...
result:
ok ok
Test #7:
score: 0
Accepted
time: 73ms
memory: 3716kb
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 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...
result:
ok ok
Test #8:
score: 0
Accepted
time: 64ms
memory: 4148kb
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 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 10...
result:
ok ok
Test #9:
score: 0
Accepted
time: 85ms
memory: 5032kb
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 35050 32825 31708 1 2 3 4 5 22702 6 7 1785 8 9 10 11 12 13 14 15 16 17 8079 18 19 20 21 22 23 24 25 26 27 28 29 46864 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 8...
result:
ok ok
Test #10:
score: 0
Accepted
time: 59ms
memory: 6404kb
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 1 2 3 92905 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...
result:
ok ok