QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#724837 | #5423. Perfect Matching | Erinyes | WA | 346ms | 53032kb | C++14 | 1.2kb | 2024-11-08 15:15:53 | 2024-11-08 15:15:53 |
Judging History
answer
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e5+5;
int n,tot,cnt;
int a[N],vst[N],del[N];
map<int,int>A,B;
vector<int>son[N<<2];
vector<pair<int,int>>ans;
void dfs(int x,int fa){
vst[x]=1,cnt+=x<=n;
vector<int> d;
for(int y:son[x]){
if(!vst[y]){
dfs(y,x);
if(x>n&&!del[y])d.push_back(y);
}
}
if(x>n){
for(int i=0;i+1<d.size();i+=2)ans.push_back({d[i],d[i+1]});
if(d.size()&1){
if(fa&&!del[fa])ans.push_back({d.back(),fa}),del[fa]=1;
}
}
}
inline void solve(){
cin>>n,tot=n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(A.find(a[i]+i)==A.end())A[a[i]+i]=++tot;
if(B.find(a[i]-i)==B.end())B[a[i]-i]=++tot;
son[i].push_back({A[a[i]+i]}),son[A[a[i]+i]].push_back(i);
son[i].push_back({B[a[i]-i]}),son[B[a[i]-i]].push_back(i);
}
for(int i=1;i<=tot;i++){
if(vst[i])continue;
cnt=0,dfs(i,0);
if(cnt&1)return cout<<"No\n",void();
}
cout<<"Yes\n";
for(auto t:ans)cout<<t.first<<' '<<t.second<<endl;
for(int i=1;i<=tot;i++)son[i].clear(),vst[i]=del[i]=0;
ans.clear();
}
signed main(){
#ifndef ONLINE_JUDGE
freopen(".in","r",stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 13904kb
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: 346ms
memory: 53032kb
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)