QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662726 | #5423. Perfect Matching | ocharin | WA | 168ms | 19436kb | C++20 | 1.6kb | 2024-10-21 09:34:49 | 2024-10-21 09:34:50 |
Judging History
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)