QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72148 | #5423. Perfect Matching | Crysfly | WA | 870ms | 41228kb | C++11 | 2.6kb | 2023-01-14 15:46:19 | 2023-01-14 15:46:23 |
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;
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)puts("No"),exit(0);
res.pb(mkp(fe[u],o[0]));
return 0;
}
return 1;
}
void work()
{
n=read();
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);
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: 2ms
memory: 23832kb
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: 389ms
memory: 33372kb
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: 1ms
memory: 21752kb
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: 409ms
memory: 41228kb
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: 870ms
memory: 32696kb
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: -100
Wrong Answer
time: 5ms
memory: 21848kb
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
result:
wrong output format Unexpected end of file - token expected (test case 2)