QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#387887 | #5423. Perfect Matching | wsc2008# | AC ✓ | 1112ms | 60336kb | C++14 | 1.9kb | 2024-04-12 22:53:57 | 2024-04-12 22:53:57 |
Judging History
answer
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void write(ll x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
const ll N=1e6+9;
ll T,n,a[N],tot,dep[N];
vector<pii>to[N],ans;
map<ll,ll>mp1,mp2;
ll dfs(ll x,ll f){
dep[x]=dep[f]+1;
vector<ll>e;
for(pii es:to[x]){
ll y=es.first,id=es.second;
if(!dep[y]){
ll ret=dfs(y,x);
if(ret)ans.push_back(make_pair(ret,id));
else e.push_back(id);
}
else if(dep[y]>dep[x])e.push_back(id);
}
rep(i,0,(ll)e.size()-2){
ans.push_back(make_pair(e[i],e[i+1]));
i++;
}
if((ll)e.size()&1)return e.back();
return 0;
}
void solve(){
n=read();
rep(i,1,n)a[i]=read();
tot=0;
mp1.clear(),mp2.clear();
rep(i,1,n){
if(!mp1.count(a[i]-i))mp1[a[i]-i]=++tot;
if(!mp2.count(a[i]+i))mp2[a[i]+i]=++tot;
}
rep(i,0,tot+1)to[i].clear();
rep(i,1,n){
to[mp1[a[i]-i]].push_back(make_pair(mp2[a[i]+i],i));
to[mp2[a[i]+i]].push_back(make_pair(mp1[a[i]-i],i));
}
rep(i,0,tot+1)dep[i]=0;
ans.clear();
rep(i,1,tot){
if(!dep[i])dfs(i,0);
}
if((ll)ans.size()!=n/2)return puts("No"),void();
puts("Yes");
for(pii p:ans)write(p.first),putchar(' '),write(p.second),putchar('\n');
}
bool Med;
int main(){
cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
T=read();
while(T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 27412kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 4 1 2 5 3 6 Yes 3 1 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 375ms
memory: 43088kb
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: 0ms
memory: 27332kb
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 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 9 30 31 32 33 34 29 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 60 61 62 63 64 65 66 67 68 59 70 71 72 73 74 69 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 75 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 395ms
memory: 60336kb
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: 1112ms
memory: 46404kb
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 89504 28 8564 26518 63463 1121 36817 129 8931 95315 96991 61541 70110 81303 13611 16772 34736 778 88310 80993 11544 74032 33052 80608 78597 37367 65442 84943 50244 20961 91157 52881 10333 6609 3408 19162 59542 87006 97729 416 79681 23980 27149 66364 67617 10211 17075 44140 57643 11472 33046 1885...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 209ms
memory: 27568kb
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 6 9 16 17 18 21 22 25 27 31 32 33 35 42 47 51 62 64 72 79 82 86 90 96 101 103 107 109 111 121 127 145 147 155 157 159 164 166 169 174 176 179 191 192 195 201 204 210 223 229 230 237 244 246 252 260 262 269 276 282 292 293 294 295 296 297 301 303 304 306 309 318 325 329 336 338 ...
result:
ok 1000 Cases (1000 test cases)