QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#759572 | #5423. Perfect Matching | wangchunjie | RE | 371ms | 27864kb | C++14 | 1.5kb | 2024-11-18 10:10:27 | 2024-11-18 10:10:27 |
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(v==pa) continue;
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<=n;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: 2ms
memory: 6660kb
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: 0
Accepted
time: 371ms
memory: 27864kb
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:
Yes 79 139 202 244 289 310 316 322 337 382 397 451 460 463 481 517 520 526 556 568 619 661 736 763 790 853 904 934 979 988 1090 1105 1162 1219 1273 1285 1294 1405 1411 1456 1459 1531 1555 1561 1588 1615 1618 1630 1651 1669 1684 1723 1738 1915 1972 2026 2029 2092 2155 2197 2290 2305 2350 2353 2419 24...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 2ms
memory: 6652kb
input:
10 100 28761184 28761185 28761186 28761187 28761188 28761189 28761190 28761191 -20675012 -20675013 -20675014 -20675015 -20675016 -20675017 -20675018 -20675019 -20675020 -20675021 -20675022 -20675023 -20675024 -20675025 -20675026 -20675027 -20675028 -20675029 -20675030 -20675031 -36758138 -36758139 -...
output:
Yes 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 39 58 29 30 31 32 33 34 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 59 60 61 62 63 64 65 66 67 68 36 37 35 38 2 3 4 5 6 7 1 8 69 70 71 72 73 74 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: -100
Runtime Error
input:
10 100000 -40608960 -40608959 -40608958 -40608957 -40608956 -40608955 -40608954 -40608953 -40608952 -40608951 -40608950 -40608949 -40608948 -40608947 -40608946 -40608945 -40608944 -40608943 -40608942 -40608941 -40608940 -40608939 -40608938 -40608937 -40608936 -40608935 -40608934 -40608933 -40608932 ...