QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#662726#5423. Perfect MatchingocharinWA 168ms19436kbC++201.6kb2024-10-21 09:34:492024-10-21 09:34:50

Judging History

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

  • [2024-10-21 09:34:50]
  • 评测
  • 测评结果:WA
  • 用时:168ms
  • 内存:19436kb
  • [2024-10-21 09:34:49]
  • 提交

answer

/*

								_/                                      _/
	   _/_/        _/_/_/      _/_/_/        _/_/_/      _/  _/_/               _/_/_/
	_/    _/    _/            _/    _/    _/    _/      _/_/          _/       _/    _/
   _/    _/    _/            _/    _/    _/    _/      _/            _/       _/    _/
	_/_/        _/_/_/      _/    _/      _/_/_/      _/            _/       _/    _/

*/
#include<bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
	int n;
	cin>>n;
	vector<int>a(n);
	for(int i=0;i<n;++i) cin>>a[i];
	unordered_map<int,int>mp;
	int cnt=0;
	vector<vector<array<int,2>>>e(2*n);
	for(int i=0;i<n;++i){
		int u=i-a[i],v=i+a[i];
		if(!mp.count(u)) mp[u]=cnt++;
		if(!mp.count(v)) mp[v]=cnt++;
		u=mp[u],v=mp[v];
		e[u].push_back({v,i+1});
		e[v].push_back({u,i+1});
	}
	vector<array<int,2>>res;
	vector<int>dep(cnt),vis(cnt);
	cerr<<" ? "<<endl;
	auto dfs=[&](auto dfs,int u)->int{
		vis[u]=1;
		int cur=0;
		for(auto [v,w]:e[u]){
			if(vis[v]){
				if(dep[v]<=dep[u]) continue;
				if(!cur){
					cur=w;
				}
				else{
					res.push_back({cur,w});
					cur=0;
				}
			}
			else{
				dep[v]=dep[u]+1;
				int x=dfs(dfs,v);
				if(x){
					res.push_back({x,w});
				}
				else{
					if(cur){
						res.push_back({w,cur});
						cur=0;
					}
					else cur=w;
				}
			}
		}
		return cur;
	};
	for(int i=0;i<cnt;++i){
		if(!vis[i]) dfs(dfs,i);
	}
	if(res.size()*2==n){
		cout<<"Yes\n";
		for(auto [x,y]:res) cout<<x<<" "<<y<<"\n";
	}
	else cout<<"No\n";
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;cin>>T;
	while(T--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3588kb

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: 168ms
memory: 19436kb

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)