QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#732275 | #5423. Perfect Matching | JoeyJ | AC ✓ | 781ms | 40836kb | C++14 | 3.0kb | 2024-11-10 13:51:09 | 2024-11-10 13:51:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ssiz(x) (signed)x.size()
#define allc(x) x.begin(),x.end()
const int N=2e5+9;
int a[N],u[N],v[N],r[N],ans[N],n,tot;
vector<pair<int,int>> e[N];
vector<int> tmp[N];
int vis[N],c[N],root;
void DFS(int x){
vis[x]=1;
for(auto p:e[x]){
int y=p.first;
if(!vis[y]){
c[y]=c[x]^1;
DFS(y);
}else if(c[y]==c[x]) root=x;
}
}
int dep[N],siv[N],fa[N];
int Solve(int x){
int cnt=r[x];
siv[x]=1;
for(auto p:e[x]){
int y=p.first;
if(siv[y]) continue ;
fa[y]=x,dep[y]=dep[x]+1;
int tmp=Solve(y);
if(tmp==1){
cnt^=1;
ans[p.second]^=1;
}
}
return cnt;
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
tot=0;
map<int,int> mp;
for(int i=1;i<=n;i++){
if(!mp[i-a[i]]) mp[i-a[i]]=++tot;
u[i]=mp[i-a[i]];
r[u[i]]^=1;
}
mp.clear();
for(int i=1;i<=n;i++){
if(!mp[i+a[i]]) mp[i+a[i]]=++tot;
v[i]=mp[i+a[i]];
}
for(int i=1;i<=n;i++){
e[u[i]].push_back({v[i],i});
e[v[i]].push_back({u[i],i});
}
int err=0;
for(int i=1,flag;i<=tot;i++){
if(vis[i]) continue ;
root=0,flag=1;
DFS(i);
if(!root) root=i,flag=0;
int cnt=Solve(root);
if(!cnt) continue ;
if(!flag){
err=1;
continue ;
}
int pos=0;
for(auto p:e[root]){
int x=p.first;
if(dep[x]&1) continue ;
pos=x;
ans[p.second]^=1;
break ;
}
vector<int> pth;
while(pos!=root){
pth.push_back(pos);
pos=fa[pos];
}
pth.push_back(root);
reverse(allc(pth));
for(int j=1;j<ssiz(pth);j++){
for(auto p:e[pth[j]]){
if(p.first!=pth[j-1]) continue ;
ans[p.second]^=1;
break ;
}
}
}
if(err) cout<<"No"<<endl;
else{
cout<<"Yes"<<endl;
for(int i=1;i<=n;i++){
if(ans[i]) tmp[v[i]].push_back(i);
else tmp[u[i]].push_back(i);
}
for(int i=1;i<=tot;i++){
for(int j=0;j<ssiz(tmp[i]);j+=2) cout<<tmp[i][j]<<' '<<tmp[i][j+1]<<endl;
}
}
for(int i=1;i<=tot;i++){
e[i].clear(),tmp[i].clear();
vis[i]=siv[i]=dep[i]=fa[i]=c[i]=r[i]=0;
}
for(int i=1;i<=n;i++){
a[i]=u[i]=v[i]=ans[i]=0;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 16116kb
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: 30572kb
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 14 15 16 20 21 32 39 42 43 45 46 47 49 56 57 58 62 63 64 65 66 68 70 71 73 74 75 77 80 81 82 87 88 95 97 101 102 103 105 106 116 117 118 137 148 155 156 158 160 164 166 167 169 171 172 176 177 182 183 184 190 191 192 193 200 208 209 210 228 229 237 238 239 241 242 243 245 247 251 252 253 254 255...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 2ms
memory: 17976kb
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 1 2 3 4 5 6 7 8 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 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 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 493ms
memory: 40836kb
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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 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 101 ...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 781ms
memory: 29672kb
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 4 6 7 8 13 23 47 57 62 63 84 107 114 122 208 210 271 274 307 417 481 489 495 507 536 548 565 659 791 1002 1122 1138 1147 1175 1256 1280 1324 1388 1414 1716 1973 2236 2386 2439 2616 2897 3257 3262 3375 3385 3412 3536 3674 3690 3779 4151 4371 4547 5149 5254 5337 5379 5575 5757 5900 5948 6377 6921 ...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 246ms
memory: 20060kb
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 1 4 11 13 23 30 34 39 40 46 48 50 53 54 58 69 73 76 88 89 92 94 105 106 108 114 116 120 123 125 128 132 133 135 137 138 148 150 153 156 163 172 173 180 181 187 188 193 194 211 222 225 227 228 236 242 254 256 261 263 275 288 289 291 299 310 317 319 343 352 355 371 389 405 407 41...
result:
ok 1000 Cases (1000 test cases)