QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#732518#5423. Perfect MatchingPorNPtreeWA 257ms13272kbC++231.5kb2024-11-10 14:58:012024-11-10 14:58:01

Judging History

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

  • [2024-11-10 14:58:01]
  • 评测
  • 测评结果:WA
  • 用时:257ms
  • 内存:13272kb
  • [2024-11-10 14:58:01]
  • 提交

answer

#include<bits/stdc++.h>
#define P pair<int,int>
#define fi first
#define se second
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=2e5+5;
int T,n,m,a[N],b[N],sz[N],fa[N];
vector<P>g[N],ans;bool v[N],ban[N];
inline int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}
inline void hb(int x,int y)
{
	x=getf(x),y=getf(y);sz[x]++;
	if(x^y) fa[y]=x,sz[x]+=sz[y];
}
inline void add(int u,int v,int w)
{
	hb(u,v);//cout<<u<<" "<<v<<" "<<w<<"\n";
	g[u].push_back({v,w}),g[v].push_back({u,w});
}
inline bool chk()
{
	for(int i=1;i<=m;i++) if(sz[getf(i)]&1) return 0;
	return 1;
}
void dfs(int x,int las)
{
	v[x]=1;
	for(auto [y,w]:g[x]) if(!v[y]) dfs(y,w);
	vector<int>nw;
	for(auto [y,w]:g[x]) if(!ban[w]&&w!=las) nw.push_back(w);
	if(nw.size()&1) nw.push_back(las);
	for(int i:nw) ban[i]=1;
	for(int i=0;i<nw.size()/2;i++) ans.push_back({nw[i<<1],nw[i<<1|1]});
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;
	while(T--)
	{
		cin>>n;m=0;ans.clear();
		for(int i=1;i<=n;i++) cin>>a[i],b[++m]=i-a[i],b[++m]=i+a[i],ban[i]=0;
		sort(b+1,b+1+m);m=unique(b+1,b+1+m)-b-1;
		for(int i=1;i<=m;i++) fa[i]=i,sz[i]=0,g[i].clear(),v[i]=0;
		#define ls(x) lower_bound(b+1,b+1+m,x)-b
		for(int i=1;i<=n;i++) add(ls(i-a[i]),ls(i+a[i]),i);
		if(!chk()){cout<<"No\n";continue;}
		for(int i=1;i<=m;i++) if(!v[i]) dfs(i,0);
		cout<<"Yes\n";
		for(auto [u,v]:ans) cout<<u<<" "<<v<<"\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5844kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

Yes
3 6
2 5
4 1
Yes
3 1
2 4
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 257ms
memory: 13272kb

input:

10
100000
0 -1 -2 -3 -4 -5 -2 -7 -8 -9 -10 -9 -12 13 14 15 -16 -17 -18 19 20 19 -22 -21 -20 -25 -26 -27 -28 -27 -26 31 30 29 -34 -35 -34 39 38 37 42 41 42 47 44 45 46 49 48 -53 -52 -51 -56 -55 -54 55 56 57 -58 -59 -60 61 62 63 64 65 64 67 66 69 70 73 72 73 74 73 76 75 74 79 80 81 -84 -83 -84 89 86 8...

output:

Yes
11 12
21 22
5 7
29 30
32 33
77 78
98 99
122 123
128 129
137 138
200 201
203 205
224 225
242 244
287 289
290 291
308 309
314 315
320 321
335 337
362 364
371 372
377 378
380 382
389 391
395 396
416 417
434 435
449 450
458 459
461 462
479 480
509 511
515 517
518 520
524 526
554 556
566 567
584 586
...

result:

wrong answer abs(3-31) != abs(a[3]-a[31]) (test case 1)