QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#733443 | #5423. Perfect Matching | oxcoxsga | WA | 7ms | 28892kb | C++14 | 1.8kb | 2024-11-10 19:01:38 | 2024-11-10 19:01:38 |
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: 0
Wrong Answer
time: 7ms
memory: 28892kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
3 Yes 1 4 2 5 3 6 2 Yes 1 3 2 4 0 No
result:
wrong answer Token parameter [name=s] equals to "3", doesn't correspond to pattern "Yes|No" (test case 1)