QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#725683 | #5423. Perfect Matching | bugmaker3243 | AC ✓ | 816ms | 31960kb | C++23 | 3.1kb | 2024-11-08 19:20:10 | 2024-11-08 19:20:11 |
Judging History
answer
#include<bits/stdc++.h>
#define N 500005
//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
#define gc() getchar()
#define fi first
#define se second
#define Kamisato return
#define Ayaka 0;
#define file(_s) freopen(#_s".in","r",stdin);freopen(#_s".out","w",stdout);
//#define CHECK_MEMORY ___JQH___
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf=1e9;
const ll INF=2e18;
bool Memory_Begin;
namespace IO{const int SIZE=(1<<21)+1;char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];int f,qr;inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf,fflush(stdout);}inline void putc(char x){*oS++=x;if(oS==oT)flush();}template <class I>inline void read(I &x){for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;}template <class I>inline void print(I x){if(!x)putc('0');if(x<0)putc('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)putc(qu[qr --]);}inline void reads(string &s){s.clear();for(c=gc();c<33||c>126;)c=gc();for(;c>=33&&c<=126;c=gc())s.push_back(c);}inline void prints(string s){for(char c:s)putc(c);}struct Flusher_ {~Flusher_(){flush();}}io_flusher_;}
using IO::read;using IO::putc;using IO::print;using IO::reads;using IO::prints;
template<class I>I updiv(I x,I y){return (x%y==0?x/y:x/y+1);}
template<class I>bool cmin(I &x,I y){if(x>y)return x=y,1;return 0;}
template<class I>bool cmax(I &x,I y){if(x<y)return x=y,1;return 0;}
int n,a[N],L,R;
map<int,int>mpL,mpR;
vector<pii>s[N];
bool vst[N];
int calc(int x)
{
queue<int>q;
q.push(x),vst[x]=1;
int res=0;
while(q.size())
{
int x=q.front();
q.pop();
res+=s[x].size();
for(pii i:s[x])
{
int y=i.fi;
if(!vst[y]) q.push(y),vst[y]=1;
}
}
return res/2;
}
vector<pii>ans;
bool usefa[N];
int dfn[N],sign;
void dfs(int x,int prt,int pre)
{
dfn[x]=++sign;
vector<int>las;
for(pii i:s[x])
{
int y=i.fi,id=i.se;
if(y==prt) continue;
if(!dfn[y])
{
dfs(y,x,id);
if(!usefa[y]) las.push_back(id);
}
else if(dfn[y]<dfn[x]) las.push_back(id);
}
if(las.size()&1) las.push_back(pre),usefa[x]=1;
for(int i=0;i+1<(int)las.size();i+=2) ans.push_back({las[i],las[i+1]});
}
void solve()
{
read(n);
for(int i=1;i<=n;i++) read(a[i]),mpL[i-a[i]]=mpR[i+a[i]]=0;
for(auto &p:mpL) p.se=++L;
for(auto &p:mpR) p.se=L+(++R);
for(int i=1;i<=n;i++)
{
int x=mpL[i-a[i]],y=mpR[i+a[i]];
s[x].push_back({y,i});
s[y].push_back({x,i});
}
for(int i=1;i<=L+R;i++)
if(!vst[i])
{
if(calc(i)&1) return prints("No\n");
dfs(i,0,0);
}
prints("Yes\n");
for(pii p:ans) print(p.fi),putc(' '),print(p.se),putc('\n');
}
void clear()
{
sign=0;
ans.clear(),mpL.clear(),mpR.clear();
for(int i=1;i<=L+R;i++) s[i].clear(),vst[i]=usefa[i]=0,dfn[i]=0;
L=R=0;
}
bool Memory_End;
signed main()
{
#ifdef CHECK_MEMORY
cerr<<"Memory: "<<(&Memory_End-&Memory_Begin)/1048576.0<<" MiB\n";
#endif
int T; read(T);
while(T--) solve(),clear();
Kamisato Ayaka
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 7584kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 3 6 2 5 4 1 Yes 3 1 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 288ms
memory: 23020kb
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 21 22 77 78 137 138 200 201 242 244 287 289 308 309 314 315 320 321 335 337 380 382 395 396 449 450 458 459 461 462 479 480 515 517 518 520 524 526 554 556 566 567 617 619 659 660 734 736 761 763 788 790 851 853 902 903 932 933 977 978 986 987 1088 1089 1103 1104 1160 1162 1217 1218 1271 1273 12...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 2ms
memory: 7736kb
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 70 71 72 73 74 69 1 2 3 4 5 6 7 8 35 36 37 38 60 61 62 63 64 65 66 67 68 59 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 9 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 30 31 32 33 34 29 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 280ms
memory: 31960kb
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 49559 49560 29353 29354 29355 29356 29357 29358 29359 29360 29361 29362 29363 29364 29365 29366 29367 29368 29369 29370 29371 29372 29373 29374 29375 29376 29377 29378 29379 29380 29381 29382 29383 29384 29385 29386 29387 29388 29389 29390 29391 29392 29393 29394 29395 29396 29397 29398 33954 33...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 816ms
memory: 24220kb
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 36811 36817 8931 95315 96991 61541 70110 81303 13611 16772 34736 778 88310 80993 821 11544 74032 940 33052 80608 9050 10585 78597 37367 41232 65442 84943 50244 91157 52881 5417 10333 18933 19162 3408 59542 87006 97729 79681 23980 27149 66364 67617 10211 17075 44140...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 154ms
memory: 9900kb
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 14 15 57 59 66 67 77 78 98 99 129 130 142 144 161 162 165 167 183 185 184 186 198 199 200 202 205 207 214 215 232 233 243 245 270 271 279 280 284 286 307 308 312 314 315 316 320 321 328 330 332 333 370 372 384 385 387 388 412 413 421 422 424 426 427 428 432 433 435 436 440 442 ...
result:
ok 1000 Cases (1000 test cases)