QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#724837#5423. Perfect MatchingErinyesWA 346ms53032kbC++141.2kb2024-11-08 15:15:532024-11-08 15:15:53

Judging History

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

  • [2024-11-08 15:15:53]
  • 评测
  • 测评结果:WA
  • 用时:346ms
  • 内存:53032kb
  • [2024-11-08 15:15:53]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e5+5;
int n,tot,cnt;
int a[N],vst[N],del[N];
map<int,int>A,B;
vector<int>son[N<<2];
vector<pair<int,int>>ans;
void dfs(int x,int fa){
	vst[x]=1,cnt+=x<=n;
	vector<int> d;
	for(int y:son[x]){
		if(!vst[y]){
			dfs(y,x);
			if(x>n&&!del[y])d.push_back(y);
		}
	}
	if(x>n){
		for(int i=0;i+1<d.size();i+=2)ans.push_back({d[i],d[i+1]});
		if(d.size()&1){
			if(fa&&!del[fa])ans.push_back({d.back(),fa}),del[fa]=1;
		}
	}
}
inline void solve(){
	cin>>n,tot=n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(A.find(a[i]+i)==A.end())A[a[i]+i]=++tot;
		if(B.find(a[i]-i)==B.end())B[a[i]-i]=++tot;
		son[i].push_back({A[a[i]+i]}),son[A[a[i]+i]].push_back(i);
		son[i].push_back({B[a[i]-i]}),son[B[a[i]-i]].push_back(i);
	}
	for(int i=1;i<=tot;i++){
		if(vst[i])continue;
		cnt=0,dfs(i,0);
		if(cnt&1)return cout<<"No\n",void();
	}
	cout<<"Yes\n";
	for(auto t:ans)cout<<t.first<<' '<<t.second<<endl;
	for(int i=1;i<=tot;i++)son[i].clear(),vst[i]=del[i]=0;
	ans.clear();
}
signed main(){
	#ifndef ONLINE_JUDGE
	freopen(".in","r",stdin);
	#endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T;cin>>T;
	while(T--)solve();
	return 0;
}

详细

Test #1:

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

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
3 1
4 2
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 346ms
memory: 53032kb

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:

No
No
No
No
No
No
No
No
No
No

result:

wrong answer std outputs a valid answer while participant doesn't (test case 1)