QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#49896#4800. Oscar's Round Must Have a Constructive ProblemCrysflyAC ✓77ms16056kbC++172.2kb2022-09-23 23:03:472022-09-23 23:03:47

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-23 23:03:47]
  • 评测
  • 测评结果:AC
  • 用时:77ms
  • 内存:16056kb
  • [2022-09-23 23:03:47]
  • 提交

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