QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#733444 | #5423. Perfect Matching | oxcoxsga | ML | 3ms | 28204kb | C++14 | 1.8kb | 2024-11-10 19:02:19 | 2024-11-10 19:02:19 |
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)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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 28204kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 2 5 3 6 Yes 1 3 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Memory Limit Exceeded
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...