QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#725683#5423. Perfect Matchingbugmaker3243AC ✓816ms31960kbC++233.1kb2024-11-08 19:20:102024-11-08 19:20:11

Judging History

你现在查看的是最新测评结果

  • [2024-11-08 19:20:11]
  • 评测
  • 测评结果:AC
  • 用时:816ms
  • 内存:31960kb
  • [2024-11-08 19:20:10]
  • 提交

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)