QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#178338#5423. Perfect MatchingdsakhdkasWA 597ms12800kbC++141.8kb2023-09-13 21:19:332023-09-13 21:19:33

Judging History

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

  • [2023-09-13 21:19:33]
  • 评测
  • 测评结果:WA
  • 用时:597ms
  • 内存:12800kb
  • [2023-09-13 21:19:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
map<int,int> mp;
vector< pair<int,int> > ans;
int T,n,a[100010],b[200010],Link[200010],dfn[200010],t,tot,sum;
bool vis[200010];
struct edge
{
	int v,nex,id;
}e[200010];
void Insert(int x,int y,int z)
{
	e[++t].nex=Link[x];e[t].v=y;Link[x]=t;e[t].id=z;return ;
}
void dfs(int now,int las)
{
	dfn[now]=++tot;vis[now]=false;
	vector <int> V;
	for (int i=Link[now];i;i=e[i].nex) {
		if (i==(las^1)) continue;
		if (!dfn[e[i].v]) {
			dfs(e[i].v,i);
			sum++;
			if (!vis[e[i].v]) 
			  V.push_back(e[i].id);
		}
		else if (dfn[e[i].v]<dfn[now]) {
			V.push_back(e[i].id);
			sum++;
		}
	}
	if ((int)V.size()&1) {
		for (int i=1;i<(int)V.size()-1;i++)
		  ans.push_back(make_pair(V[i],V[i+1]));
		ans.push_back(make_pair(V[0],e[las].id));
		vis[now]=true;
	}
	else 
	  for (int i=0;i<(int)V.size()-1;i++)
		ans.push_back(make_pair(V[i],V[i+1]));
	return ;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>T;
	for (int i1=1;i1<=T;i1++) {
		cin>>n;int nu=0;
		for (int i=1;i<=n;i++) {
		    cin>>a[i];
		    b[++nu]=a[i]-i;
		    b[++nu]=a[i]+i;
		}
		sort(b+1,b+nu+1);
		int cnt=0;
		mp.clear();
		for (int i=1;i<=nu;i++)
		  if (mp.find(b[i])==mp.end()) mp[b[i]]=++cnt;
		t=1;
		for (int i=1;i<=cnt;i++) Link[i]=0;
		for (int i=1;i<=n;i++)
		  Insert(mp[a[i]-i],mp[i+a[i]],i),Insert(mp[a[i]+i],mp[a[i]-i],i);
		bool fla=true;ans.clear();
		for (int i=1;i<=cnt;i++) dfn[i]=0;
		for (int i=1;i<=cnt;i++)
		  if (!dfn[i]) {
		  	  tot=0;sum=0;dfs(i,0);
		  	  if (sum&1) {fla=false;break;}
		  }
		if (!fla) cout<<"No"<<'\n';
		  else {
		  	  cout<<"Yes"<<'\n';
		  	  for (int i=0;i<(int)ans.size();i++)
		  	    cout<<ans[i].first<<' '<<ans[i].second<<'\n';
		  }
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 597ms
memory: 12800kb

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
99977 99979
99821 99823
99988 99986
99980 99981
99976 99974
99970 99968
99949 99947
99929 99930
99922 99921
99909 99908
99904 99902
99891 99890
99880 99878
99846 99847
99835 99833
99827 99828
99810 99811
99805 99804
99802 99800
99789 99788
99786 99787
99782 99783
99777 99778
99775 99774
99755 99...

result:

wrong answer 99892 appears more than once (test case 1)