QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#72150#5423. Perfect MatchingCrysflyAC ✓923ms40620kbC++112.7kb2023-01-14 15:47:162023-01-14 15:48:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-14 15:48:58]
  • 评测
  • 测评结果:AC
  • 用时:923ms
  • 内存:40620kb
  • [2023-01-14 15:47:16]
  • 提交

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;
}

详细

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)