QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#733443#5423. Perfect MatchingoxcoxsgaWA 7ms28892kbC++141.8kb2024-11-10 19:01:382024-11-10 19:01:38

Judging History

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

  • [2024-11-10 19:01:38]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:28892kb
  • [2024-11-10 19:01:38]
  • 提交

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();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 28892kb

input:

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

output:

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

result:

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