QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#49896 | #4800. Oscar's Round Must Have a Constructive Problem | Crysfly | AC ✓ | 77ms | 16056kb | C++17 | 2.2kb | 2022-09-23 23:03:47 | 2022-09-23 23:03:47 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define mod 998244353
struct modint{
int x;
modint(int o=0){x=o;}
modint &operator = (int o){return x=o,*this;}
modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
modint &operator ^=(int b){
modint a=*this,c=1;
for(;b;b>>=1,a*=a)if(b&1)c*=a;
return x=c.x,*this;
}
modint &operator /=(modint o){return *this *=o^=mod-2;}
friend modint operator +(modint a,modint b){return a+=b;}
friend modint operator -(modint a,modint b){return a-=b;}
friend modint operator *(modint a,modint b){return a*=b;}
friend modint operator /(modint a,modint b){return a/=b;}
friend modint operator ^(modint a,int b){return a^=b;}
bool operator ! () {return !x;}
modint operator - () {return x?mod-x:0;}
};
inline modint qpow(modint x,int y){return x^y;}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 200005
#define inf 0x3f3f3f3f
int n,a[maxn],res[maxn],b[maxn];
bool vis[maxn];
vi p[maxn];
bool cmp(int x,int y){
return p[x].size()>p[y].size();
}
signed main()
{
int T=read();
while(T--){
n=read();
For(i,1,n)a[i]=read(),b[i]=i,p[i].clear(),vis[i]=0;
int mx=0;
For(i,1,n)p[a[i]].pb(i),mx=max(mx,(int)p[a[i]].size());
if(mx==n){
puts("NO");
continue;
}
sort(b+1,b+n+1,cmp);
vi o;
Rep(i,n,1){
int v=b[i];
if(p[v].size()){
int t=p[v].back(); p[v].pop_back();
res[t]=b[1]; vis[t]=1;
break;
}
}
o=p[b[1]];
For(i,2,n){
assert(o.size()>0);
res[o.back()]=b[i]; o.pop_back();
for(auto t:p[b[i]]) if(!vis[t]) o.pb(t);
}puts("YES");
For(i,1,n) cout<<res[i]<<' '; puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8332kb
input:
3 3 3 3 3 3 3 2 1 6 1 1 4 5 1 4
output:
NO YES 1 3 2 YES 6 3 2 1 4 5
result:
ok ok
Test #2:
score: 0
Accepted
time: 37ms
memory: 8224kb
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 2 3 1 YES 2 1 3 YES 2 1 3 YES 3 2 1 YES 1 3 2 YES 3 2 1 YES 3 2 1 YES 3 1 2 NO YES 1 3 2 YES 3 1 2 YES 1 2 3 YES 3 1 2 YES 1 2 3 YES 1 2 3 YES 2 3 1 YES 1 3 2 YES 2 1 3 YES 1 3 2 YES 2 1 3 YES 1 2 3 NO ...
result:
ok ok
Test #3:
score: 0
Accepted
time: 12ms
memory: 8212kb
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: 42ms
memory: 8296kb
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 10 9 8 7 5 3 4 2 1 6 YES 5 10 9 8 7 6 3 2 1 4 YES 10 9 7 6 5 4 3 8 2 1 YES 10 9 8 7 5 4 3 1 2 6 YES 10 9 8 4 7 6 3 2 1 5 YES 9 1 8 7 6 3 2 10 4 5 YES 1 3 2 7 9 6 5 4 8 10 NO YES 8 7 6 4 5 3 2 1 10 9 YES 10 9 8 7 6 4 5 3 2 1 YES 10 9 8 7 3 2 4 1 6 5 NO NO YES 10 8 7 9 5 2 4 1 3 6 YES 5...
result:
ok ok
Test #5:
score: 0
Accepted
time: 49ms
memory: 8472kb
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 79 80 81 27 28 29 30 31 32 33 82 34 83 84 85 35 86 87 51 89 36 38 90 91 92 93 1 94 40 41 42 43 95 44 45 46 96 47 97 98 99 100 48 88 52 53 49 54 55 50 56 57 59 39 60 61 2 62 3 4 5 6 63 76 7 8 9 65 66 10 11 67 68 12 69 26 14 70 15 16 17 71 18 19 72 20 21 22 73 23 24 25 74 13 77 75 78 64 58 37 YES...
result:
ok ok
Test #6:
score: 0
Accepted
time: 38ms
memory: 11440kb
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 344 343 342 341 340 339 338 337 336 335 334 333 332 331 1 329 328 327 326 325 324 323 322 321 320 319 318 317 316 315 330 375 374 373 372 371 370 369 368 367 366 365 364 363 362 345 360 359 358 357 356 355 354 353 352 351 350 349 348 347 346 361 281 280 279 278 277 276 275 274 273 272 2...
result:
ok ok
Test #7:
score: 0
Accepted
time: 49ms
memory: 13000kb
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 3340 3339 3338 3337 3336 3335 3334 3333 1 3331 3330 3329 3328 3327 3326 3325 3324 3323 3332 3360 3359 3358 3357 3356 3355 3354 3353 3352 3341 3350 3349 3348 3347 3346 3345 3344 3343 3342 3351 3301 3300 3299 3298 3297 3296 3295 3294 3322 3292 3291 3290 3289 3288 3287 3286 3285 3284 3293 3321 3320...
result:
ok ok
Test #8:
score: 0
Accepted
time: 61ms
memory: 13168kb
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 8328 8329 8330 8331 8332 8333 8334 8335 8336 8337 8338 1 8340 8341 8342 8343 8344 8345 8346 8347 8348 8349 8350 8339 8304 8305 8306 8307 8308 8309 8310 8311 8312 8313 8314 8327 8316 8317 8318 8319 8320 8321 8322 8323 8324 8325 8326 8315 8377 8378 8379 8380 8381 8382 8383 8384 8385 8386 8387 8351...
result:
ok ok
Test #9:
score: 0
Accepted
time: 77ms
memory: 14092kb
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 11590 5502 22255 11589 22192 5501 11331 11587 16676 5500 11586 27917 22191 11585 5499 5498 22190 22189 5497 27916 16675 16674 44229 5496 22188 16673 44228 11584 5495 22187 27915 11583 16672 27914 16671 39062 5507 44227 27913 16670 11582 44213 22186 5639 22185 44225 27912 11581 44224 39061 16669 ...
result:
ok ok
Test #10:
score: 0
Accepted
time: 47ms
memory: 16056kb
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 83328 83329 83330 83331 33328 33329 83332 33330 83333 33331 83334 83335 83336 33332 33333 33334 83337 33335 75000 83339 83340 83341 33336 33337 33338 50002 83342 83343 83344 33340 33341 83345 83346 33342 83347 33343 83348 33344 33345 83349 33346 33347 83338 33348 83303 83304 33349 33350 83305 83...
result:
ok ok