QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#759564 | #5423. Perfect Matching | wangchunjie | WA | 251ms | 21940kb | C++14 | 1.5kb | 2024-11-18 10:07:12 | 2024-11-18 10:07:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int T,n,a[N],dep[N];
map<int,int> x,y;
vector<pair<int,int>> ans,G[N];
int dfs(int u,int pa)
{
dep[u]=dep[pa]+1;
vector<int> vec;
for(auto i:G[u]){
int v=i.first,id=i.second;
if(dep[v]){
if(dep[v]>dep[u])
vec.emplace_back(id);
continue;
}
int res=dfs(v,u);
if(res) ans.emplace_back(id,res);
else vec.emplace_back(id);
}
int res=0;
if(vec.size()&1) res=vec.back(),vec.pop_back();
for(int i=0;i<vec.size();i+=2)
ans.emplace_back(vec[i],vec[i+1]);
return res;
}
void solve()
{
x.clear(),y.clear(),ans.clear();
memset(dep,0,sizeof(dep));
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
x[a[i]+i]=1,y[a[i]-i]=1;
int cnt=0;
for(auto &i:x) i.second=++cnt;
for(auto &i:y) i.second=++cnt;
for(int i=1;i<=cnt;i++)
G[i].clear();
for(int i=1;i<=cnt;i++){
int u=x[a[i]+i],v=y[a[i]-i];
G[u].emplace_back(v,i);
G[v].emplace_back(u,i);
}
for(int i=1;i<=cnt;i++){
if(dep[i]) continue;
if(dfs(i,0))
return cout<<"No\n",void();
}
cout<<"Yes\n";
for(auto i:ans)
cout<<i.first<<' '<<i.second<<'\n';
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>T;
while(T--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7052kb
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 2 4 1 3 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 251ms
memory: 21940kb
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 Yes 53 59 62 80 92 110 122 173 194 200 209 254 275 299 317 335 341 353 374 389 407 449 488 533 563 581 590 611 614 629 635 647 737 761 842 878 887 980 1034 1250 1253 1367 1403 1466 1472 1526 1604 1742 1808 1814 1820 1838 1844 1931 1946 2039 2051 2114 2129 2180 2222 2225 2231 2243 2273 2303 240...
result:
wrong answer std outputs a valid answer while participant doesn't (test case 1)