QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#706260 | #5423. Perfect Matching | CSQ | AC ✓ | 885ms | 23960kb | C++17 | 2.2kb | 2024-11-03 09:51:14 | 2024-11-03 09:51:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i < b;i++)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x.size())
typedef long long int ll;
typedef pair<ll,ll> pii;
typedef vector<int> vi;
#define fi first
#define se second
const int MAXN = 2e5+5;
unordered_map<int,vector<int>>adj[2];
unordered_map<int,int>deg[2],vis[2];
int rg[MAXN],tree[MAXN];
vector<int>comp;
void dfs(int c,int v,int p){
if(!c)comp.push_back(v);
vis[c][v] = 1;
for(int x:adj[c][v]){
if(x==p)continue;
if(!vis[c^1][x]){
int i = (v-x)/2;
i = abs(i);
tree[i] = 1;
dfs(c^1,x,v);
}
}
}
void dfs2(int c,int v,int p){
for(int x:adj[c][v]){
if(x==p)continue;
int i = (v-x)/2;
i = abs(i);
if(!tree[i])continue;
dfs2(c^1,x,v);
if(deg[c^1][x]){
rg[i] = 1;
deg[c][v] ^= 1;
}
}
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
bool ok = 1;
vector<int>a(n);
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<2;i++){
adj[i].clear();
vis[i].clear();
deg[i].clear();
}
for(int i=0;i<n;i++)rg[i] = tree[i] = 0;
for(int i=0;i<n;i++){
adj[0][a[i]-i].push_back(a[i]+i);
adj[1][a[i]+i].push_back(a[i]-i);
}
for(auto x:adj[0])deg[0][x.fi] = sz(x.se)%2;
for(int i=0;i<n;i++){
if(vis[0][a[i]-i])continue;
comp.clear();
dfs(0,a[i]-i,-2e9);
int sum = 0;
for(int v:comp){
sum += deg[0][v];
for(int x:adj[0][v]){
int j = (v-x)/2;
j = abs(j);
if(!tree[j]){
rg[j] = 1;
deg[0][v] ^= 1;
deg[1][x] ^= 1;
}
}
}
dfs2(0,comp[0],-2e9);
if(sum&1){
ok = 0;
break;
}
}
if(!ok){
cout<<"No"<<'\n';
continue;
}
map<int,vector<int>>l,r;
for(int i=0;i<n;i++){
//cout<<a[i]-i<<" "<<a[i]+i<<" "<<rg[i]<<'\n';
if(rg[i])r[a[i]+i].push_back(i);
else l[a[i]-i].push_back(i);
}
cout<<"Yes"<<'\n';
for(auto x:l){
vector<int>v = x.se;
for(int i=0;i<sz(v);i+=2){
cout<<v[i]+1<<" "<<v[i+1]+1<<'\n';
}
}
for(auto x:r){
vector<int>v = x.se;
for(int i=0;i<sz(v);i+=2){
cout<<v[i]+1<<" "<<v[i+1]+1<<'\n';
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 2 5 3 6 1 4 Yes 2 4 1 3 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 394ms
memory: 18816kb
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 140 142 34 79 139 202 310 316 322 397 451 460 463 481 568 661 904 934 979 988 1090 1105 1219 1294 1459 1531 1555 1561 1618 1669 1684 1723 1738 2026 2029 2155 2197 2290 2419 2485 2509 2530 2551 2602 2692 2695 2800 2818 2821 2890 2914 2923 3061 3142 3154 3343 3496 3589 3784 3916 3952 3988 4060 406...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3632kb
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 35 36 37 38 1 2 3 4 5 6 7 8 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 69 70 71 72 73 74 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 288ms
memory: 23960kb
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 ...
output:
Yes 71753 71754 71755 71756 71757 71758 71759 71760 71761 71762 71763 71764 71765 71766 71767 71768 71769 71770 71771 71772 71773 71774 71775 71776 71777 71778 71779 71780 71781 71782 71783 71784 71785 71786 71787 71788 71789 71790 71791 71792 71793 71794 71795 71796 71797 71798 71799 71800 71801 71...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 885ms
memory: 22280kb
input:
10 100000 0 -1 -2 3 2 5 6 7 -2 1 0 9 12 11 -8 13 8 -7 16 17 -10 19 22 21 22 23 4 -15 -18 -17 -6 -31 -14 25 32 -25 26 27 -32 31 38 -31 -32 -19 -30 -35 46 45 -48 -37 48 41 46 -43 -44 53 56 55 50 -27 52 61 62 -33 -18 19 64 45 46 -57 -8 -25 -26 -11 -22 49 -66 -65 -66 29 78 -15 74 83 12 83 14 85 86 -7 -5...
output:
Yes 99327 99702 97303 99263 95828 96046 95341 97927 93823 98919 97616 97711 93730 94937 95342 98589 93180 97318 92136 96630 93829 95270 94735 96521 91620 94320 92059 92301 91889 93560 93095 95731 91882 96890 90459 91338 97295 98433 90174 92734 96660 99305 98913 99486 93567 98857 89088 98883 92401 98...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 218ms
memory: 3900kb
input:
1000 1000 -2 0 3 4 6 7 4 7 6 9 11 9 10 12 16 13 16 17 18 20 19 19 24 22 25 23 28 25 26 27 30 32 31 34 36 37 34 37 37 40 42 43 44 45 43 44 46 45 50 48 51 49 54 55 52 55 54 57 56 61 60 61 64 65 64 67 65 66 67 68 71 73 73 75 76 77 78 75 76 78 82 79 80 81 83 83 87 88 90 89 90 93 92 93 95 94 96 96 100 97...
output:
No No No No No No Yes 2 8 10 19 44 52 60 63 80 84 95 97 100 115 117 140 168 189 196 197 206 209 216 217 218 234 238 239 247 248 253 258 264 265 281 290 305 322 327 353 360 362 369 379 380 408 420 430 441 448 457 475 479 481 488 493 495 496 498 526 531 532 534 541 556 562 567 569 571 582 595 621 622 ...
result:
ok 1000 Cases (1000 test cases)