QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91707#5423. Perfect MatchingWolamTL 2ms11632kbC++141.6kb2023-03-29 14:02:542023-03-29 14:02:55

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:02:55]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:11632kb
  • [2023-03-29 14:02:54]
  • 提交

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;
		}
		else now=i;
	}
	if(now&&f)
	{
		ans[++len]=make_pair(now>>1,f>>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);
		//cerr<<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: 2ms
memory: 11632kb

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
Time Limit Exceeded

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:


result: