QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#86586 | #4800. Oscar's Round Must Have a Constructive Problem | chimera# | AC ✓ | 1671ms | 17524kb | C++17 | 3.4kb | 2023-03-10 10:47:11 | 2023-03-10 10:47:14 |
Judging History
answer
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>
#include <utility>
#define greedy int
#define mindset main()
using namespace std;
#define FOR(a,b,c) for(int a = b; a < (c); a++)
#define FORR(a,b,c) for(int a = b; a > (c); a--)
#define READ(x) long long x;cin>>x;
#define READAR(x,n) vll x(n); FOR(readar,0,n) cin >> x[readar];
#define speedfirst ios_base::sync_with_stdio(false); cin.tie(NULL);
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef tuple<ll,ll,ll> tll;
ll MOD = 998244353;
/*//Combinatorics mod MOD
vll FACT(1e5);
ll fastexp(ll a, ll p) {
ll r = 1;
while(p) {
if(p&1) r = r*a % MOD;
a = a*a % MOD;
p >>= 1;
}
return r;
}
ll modinv(ll x) {
return fastexp(x,MOD-2);
}
void DOFACTS() {
FACT[0] = 1;
FOR(i,1,FACT.size()) {
FACT[i] = i*FACT[i-1] % MOD;
}
}
ll gcd(ll a, ll b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
*/
//segment tree, courtesy of https://cp-algorithms.com/data_structures/segment_tree.html
/*
int tree[4*200000];
void build(int v, int tl, int tr) {
if (tl == tr) {
tree[v] = 0;
} else {
int tm = (tl + tr) / 2;
build(v*2, tl, tm);
build(v*2+1, tm+1, tr);
tree[v] = tree[v*2] + tree[v*2+1];
}
}
int sum(int v, int tl, int tr, int l, int r) {
if (l > r)
return 0;
if (l == tl && r == tr) {
return tree[v];
}
int tm = (tl + tr) / 2;
return sum(v*2, tl, tm, l, min(r, tm))
+ sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}
void update(int v, int tl, int tr, int pos, int new_val) {
if (tl == tr) {
tree[v] = new_val;
} else {
int tm = (tl + tr) / 2;
if (pos <= tm)
update(v*2, tl, tm, pos, new_val);
else
update(v*2+1, tm+1, tr, pos, new_val);
tree[v] = tree[v*2] + tree[v*2+1];
}
}
void add(int v, int tl, int tr, int pos, int new_val) {
if (tl == tr) {
tree[v] += new_val;
} else {
int tm = (tl + tr) / 2;
if (pos <= tm)
add(v*2, tl, tm, pos, new_val);
else
add(v*2+1, tm+1, tr, pos, new_val);
tree[v] = tree[v*2] + tree[v*2+1];
}
}
*/
greedy mindset {
speedfirst;
READ(T);
FOR(t,0,T) {
READ(N); READAR(A, N);
map<ll,vll> CA;
FOR(i,0,N) {
CA[A[i]].push_back(i);
}
if(CA[A[0]].size() == N) {
cout << "NO\n"; continue;
}
vll X(N);
FOR(i,0,N) X[i] = i+1;
sort(X.begin(), X.end(), [&](ll x, ll y) {
return (CA[x].size() > CA[y].size()) || ((CA[x].size() == CA[y].size()) && (x > y));
});
vll P(N,-1);
FOR(i,0,N) {
if(!(CA[i].size())) CA.erase(i);
}
FOR(i,0,N) {
auto it = CA.begin();
if((*it).first == X[i]) ++it;
P[(*it).second.back()] = X[i];
(*it).second.pop_back();
if(!(*it).second.size()) {
CA.erase(it);
}
}
cout << "YES\n";
FOR(i,0,N) {
cout << P[i] << (i == N-1 ? '\n' : ' ');
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3452kb
input:
3 3 3 3 3 3 3 2 1 6 1 1 4 5 1 4
output:
NO YES 2 1 3 YES 6 5 3 2 4 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 70ms
memory: 3448kb
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 2 3 1 YES 3 1 2 YES 2 3 1 YES 3 1 2 YES 2 1 3 YES 3 2 1 YES 3 2 1 YES 1 3 2 YES 3 2 1 YES 1 3 2 YES 3 1 2 NO YES 1 3 2 YES 1 2 3 YES 1 2 3 YES 3 1 2 YES 1 2 3 YES 2 3 1 YES 2 3 1 YES 2 1 3 YES 2 1 3 YES 1 3 2 YES 2 1 3 YES 1 2 3 NO NO YES 3 4 2 1 YES 2 4 3 1...
result:
ok ok
Test #3:
score: 0
Accepted
time: 16ms
memory: 3416kb
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: 157ms
memory: 3416kb
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 4 5 7 3 8 9 10 6 YES 5 1 2 3 6 7 8 9 10 4 YES 2 3 4 5 6 7 9 8 10 1 YES 1 3 4 5 7 8 9 10 2 6 YES 1 2 3 4 6 7 8 9 10 5 YES 7 6 8 9 5 1 2 10 4 3 YES 5 1 2 4 7 9 8 6 3 10 NO YES 7 8 1 4 2 3 5 6 9 10 YES 2 3 5 6 7 4 8 9 10 1 YES 4 7 8 9 1 2 10 3 6 5 NO NO YES 1 2 4 3 5 10 7 6 8 9 YES 1 7 10 2 6 9...
result:
ok ok
Test #5:
score: 0
Accepted
time: 354ms
memory: 3544kb
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 53 54 55 1 2 3 4 5 6 7 56 8 57 59 60 9 61 62 63 64 10 11 65 66 67 68 12 69 13 14 15 16 70 17 18 19 71 20 72 73 74 75 21 76 77 78 22 79 80 23 81 82 83 24 84 85 25 86 26 27 28 29 87 88 30 31 32 89 90 33 34 91 92 35 93 36 38 94 39 40 41 95 42 43 96 44 45 46 97 47 48 49 98 50 51 99 52 100 58 37 YES ...
result:
ok ok
Test #6:
score: 0
Accepted
time: 547ms
memory: 3616kb
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 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...
result:
ok ok
Test #7:
score: 0
Accepted
time: 829ms
memory: 4736kb
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 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 #8:
score: 0
Accepted
time: 1019ms
memory: 6804kb
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 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 #9:
score: 0
Accepted
time: 1671ms
memory: 10108kb
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 14229 21372 28521 14230 28522 21373 14231 14232 35694 21374 14233 1 28523 14234 21375 21376 28524 28525 21377 2 35695 35696 42870 21378 28526 35697 42871 14235 21379 28527 3 14236 35698 4 35699 7089 21380 42872 5 35700 14237 42873 28528 21381 28529 42874 6 14238 42875 7090 35701 7091 28530 28531...
result:
ok ok
Test #10:
score: 0
Accepted
time: 1306ms
memory: 17524kb
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 50004 50005 50006 50007 2 3 50008 4 50009 5 50010 50011 50012 6 7 8 50013 9 50014 50015 50016 50017 10 11 12 13 50018 50019 50020 14 15 50021 50022 16 50023 17 50024 18 19 50025 20 21 50026 22 50027 50028 23 24 50029 50030 50031 25 26 27 50032 50033 50034 50035 50036 50037 28 29 50038 30 50039 3...
result:
ok ok