QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#733453#5423. Perfect MatchingoxcoxsgaML 6ms28144kbC++141.8kb2024-11-10 19:06:052024-11-10 19:06:14

Judging History

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

  • [2024-11-10 19:06:14]
  • 评测
  • 测评结果:ML
  • 用时:6ms
  • 内存:28144kb
  • [2024-11-10 19:06:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MaxN=1000000;
int n,a[MaxN+1],btr=0;
vector<int>g[MaxN+1];
bool vst[MaxN+1];
vector<pair<int,int>>ans;
pair<vector<int>,bool>DFS(int u,int prt){
	vst[u]=true;
	vector<int>clt;
	for(int v:g[u]){
		if(v==prt)continue;
		auto ret=DFS(v,u);
		auto&vec=ret.first;
		if(!ret.second)return make_pair(vector<int>(),false);
		clt.insert(clt.end(),vec.begin(),vec.end());
	}
	if(u>n){
		while(clt.size()>=2){
			ans.emplace_back(clt[clt.size()-1],clt[clt.size()-2]);
			clt.pop_back(),clt.pop_back();
		}
		return make_pair(clt,true);
	}else{
		if(clt.size()==0){
			return make_pair(vector<int>{u},true);
		}else if(clt.size()==1){
			ans.emplace_back(u,clt.back());
			return make_pair(vector<int>(),true);
		}else return make_pair(vector<int>(),false);
	}
}
void Solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	unordered_map<int,vector<int> >umap;
	for(int i=1;i<=n*3;i++)g[i].clear(),vst[i]=false;
	ans.clear();
	btr=0;
	for(int i=1;i<=n;i++)umap[a[i]+i].push_back(i);
	for(auto&pi:umap){
		if(pi.second.size()<2)continue;
		btr++;
		for(int v:pi.second){
			g[btr+n].push_back(v);
			g[v].push_back(btr+n);
		}
	}
	umap.clear();
	for(int i=1;i<=n;i++)umap[a[i]-i].push_back(i);
	for(auto&pi:umap){
		if(pi.second.size()<2)continue;
		btr++;
		for(int v:pi.second){
			g[btr+n].push_back(v);
			g[v].push_back(btr+n);
		}
	}
//	cout<<btr<<'\n';
	for(int i=1;i<=n;i++){
		if(vst[i])continue;
		auto ret=DFS(i,0);
		if(!ret.second||ret.first.size()){
			cout<<"No\n";
			return;
		}
	}
	cout<<"Yes\n";
	for(auto&pi:ans)cout<<pi.first<<' '<<pi.second<<'\n';
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin.tie(0)->sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--){
		Solve();
		if(T>8)throw"hbr";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 28144kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Memory 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: