QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72150 | #5423. Perfect Matching | Crysfly | AC ✓ | 923ms | 40620kb | C++11 | 2.7kb | 2023-01-14 15:47:16 | 2023-01-14 15:48:58 |
Judging History
answer
// what is matter? never mind.
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
//#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
int mod;
struct modint{
int x;
modint(int o=0){x=o;}
modint &operator = (int o){return x=o,*this;}
modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
modint &operator ^=(int b){
modint a=*this,c=1;
for(;b;b>>=1,a*=a)if(b&1)c*=a;
return x=c.x,*this;
}
modint &operator /=(modint o){return *this *=o^=mod-2;}
friend modint operator +(modint a,modint b){return a+=b;}
friend modint operator -(modint a,modint b){return a-=b;}
friend modint operator *(modint a,modint b){return a*=b;}
friend modint operator /(modint a,modint b){return a/=b;}
friend modint operator ^(modint a,int b){return a^=b;}
friend bool operator ==(modint a,int b){return a.x==b;}
friend bool operator !=(modint a,int b){return a.x!=b;}
bool operator ! () {return !x;}
modint operator - () {return x?mod-x:0;}
bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 500005
#define inf 0x3f3f3f3f
int n,a[maxn],bel1[maxn],bel2[maxn],m;
bool ok;
map<int,int>mp;
int ID(int x){
if(!mp.count(x))return mp[x]=++m;
return mp[x];
}
vector<pii>e[maxn],res;
int dep[maxn],fe[maxn];
bool dfs(int u,int pa){
dep[u]=dep[pa]+1;
vi o;
for(auto it:e[u]){
int v=it.fi,i=it.se;
if(i==fe[u])continue;
if(!dep[v]){
fe[v]=i;
if(dfs(v,u)) o.pb(i);
}
else if(dep[v]<dep[u])o.pb(i);
}
while(o.size()>=2) res.pb(mkp(o.back(),o[o.size()-2])),o.pop_back(),o.pop_back();
if(o.size()&1){
if(!pa)ok=0;
res.pb(mkp(fe[u],o[0]));
return 0;
}
return 1;
}
void work()
{
n=read();ok=1;
For(i,0,n*2)e[i].clear(),dep[i]=fe[i]=0; mp.clear(),res.clear(),m=0;
For(i,1,n)a[i]=read(),bel1[i]=ID(a[i]+i);
mp.clear();
For(i,1,n){
bel2[i]=ID(a[i]-i);
e[bel1[i]].pb(mkp(bel2[i],i));
e[bel2[i]].pb(mkp(bel1[i],i));
}
For(i,1,m)if(!dep[i])dfs(i,0);
if(!ok){puts("No");return;}
puts("Yes");
for(auto t:res)cout<<t.fi<<" "<<t.se<<"\n";
}
signed main()
{
int T=read();
while(T--)work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 21700kb
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: 392ms
memory: 33336kb
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 78 77 138 137 201 200 244 242 289 287 309 308 315 314 321 320 337 335 382 380 396 395 450 449 459 458 462 461 480 479 517 515 520 518 526 524 556 554 567 566 619 617 660 659 736 734 763 761 790 788 853 851 903 902 933 932 978 977 987 986 1089 1088 1104 1103 1162 1160 1218 1217 1273 1271 1285 128...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 3ms
memory: 23828kb
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 8 7 6 5 4 3 1 2 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 34 33 32 31 30 29 38 37 35 36 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 39 40 68 67 66 65 64 63 62 61 60 59 74 73 72 71 70 69 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 442ms
memory: 40620kb
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 274 273 272 271 270 269 268 267 266 265 264 263 262 261 260 259 258 257 256 255 254 253 252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 ...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 923ms
memory: 32480kb
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 28 89504 63463 26518 1121 8564 36817 36811 95315 8931 61541 96991 92548 81132 83637 41302 778 34736 4360 12537 2005 99552 92893 97953 30631 58176 19622 70597 26691 37677 67617 66364 10211 27149 57643 44140 11472 17075 95323 35741 12598 23176 10585 9050 28519 68565 10746 21782 63141 47710 5564 17...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 189ms
memory: 22040kb
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 22 23 33 34 47 48 72 73 107 108 127 128 147 148 155 156 179 180 192 193 210 211 260 261 262 263 309 310 318 319 342 343 404 405 406 407 417 418 443 444 455 456 502 503 583 584 599 600 663 664 699 700 704 705 718 719 720 721 727 728 739 740 770 771 857 858 912 913 951 952 962 96...
result:
ok 1000 Cases (1000 test cases)