QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91722#5423. Perfect MatchingWolamWA 226ms11496kbC++141.7kb2023-03-29 14:37:322023-03-29 14:37:34

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-29 14:37:34]
  • 评测
  • 测评结果:WA
  • 用时:226ms
  • 内存:11496kb
  • [2023-03-29 14:37:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005],b[2][100005];
int vis[400005],head[200005],tot;
int h[400005];
struct ss{
	int node,nxt;
}e[400005];
void add(int u,int v)
{
	e[++tot].nxt=head[u];
	e[tot].node=v;
	head[u]=tot;
}
pair<int,int> ans[100005];
int len;
void dfs(int x,int fa)
{
//	cerr<<x<<endl;
	int now=0;
	int f=0;
	h[x]=1;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int y=e[i].node;
		if(vis[i])continue;
		if(y==fa)
		{
			f=i;
			continue;
		}
		if(!h[y]) 
			dfs(y,x);
		if(now)
		{
			ans[++len]=make_pair(now>>1,i>>1);
			vis[i]=vis[i^1]=vis[now]=vis[now^1]=1;
			now=0;
		}
		else now=i;
	}
	if(now&&f)
	{
		ans[++len]=make_pair(now>>1,f>>1);
		vis[now]=vis[now^1]=vis[f]=vis[f^1]=1;
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
//	scanf("%d",&T);
	while(T--)
	{
		cin>>n;
		tot=1;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			b[0][i]=i+a[i];
			b[1][i]=i-a[i];
		}
		sort(b[0]+1,b[0]+n+1);
		sort(b[1]+1,b[1]+n+1);
		b[0][0]=unique(b[0]+1,b[0]+n+1)-b[0]-1;
		b[1][0]=unique(b[1]+1,b[1]+n+1)-b[1]-1;
		for(int i=1;i<=b[0][0]+b[1][0];i++)
			h[i]=head[i]=0;
		for(int i=1;i<=n;i++)
		{
			int x=lower_bound(b[0]+1,b[0]+b[0][0]+1,a[i]+i)-b[0];
			int y=lower_bound(b[1]+1,b[1]+b[1][0]+1,i-a[i])-b[1];
		//	cerr<<x<<" "<<y<<endl;
			add(x,y+b[0][0]);add(y+b[0][0],x); 
		}
		for(int i=1;i<=tot;i++)
			vis[i]=0;
		len=0;
		for(int i=1;i<=b[0][0]+b[1][0];i++)
			if(!h[i])dfs(i,0);
		if(n==100000)cout<<tot<<" "<<len<<endl;
		if(len==n/2)
		{
			cout<<"Yes\n";
			for(int i=1;i<=len;i++)
				cout<<ans[i].first<<" "<<ans[i].second<<'\n';
		}
		else cout<<"No\n";
	}
}
/*
1
3 18 33
UDRLR
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 7552kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 226ms
memory: 11496kb

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:

200001 58341
No
200001 58421
No
200001 58382
No
200001 58269
No
200001 58379
No
200001 58425
No
200001 58422
No
200001 58311
No
200001 58318
No
200001 58351
No

result:

wrong answer Token parameter [name=s] equals to "200001", doesn't correspond to pattern "Yes|No" (test case 1)