QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#733517 | #5423. Perfect Matching | oxcoxsga | WA | 0ms | 28360kb | C++14 | 2.0kb | 2024-11-10 19:35:29 | 2024-11-10 19:35:29 |
Judging History
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||!vst[v])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++;
//cout<<pi.first<<"(p):";
for(int v:pi.second){
// cout<<v<<' ';
g[btr+n].push_back(v);
g[v].push_back(btr+n);
}
//cout<<'\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++;
//cout<<pi.first<<"(n):";
for(int v:pi.second){
// cout<<v<<' ';
g[btr+n].push_back(v);
g[v].push_back(btr+n);
}
//cout<<'\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';
}
/*
1
7
1 4 1 10 1 1 7
*/
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: 0ms
memory: 28360kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
No No No
result:
wrong answer std outputs a valid answer while participant doesn't (test case 1)