QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72148#5423. Perfect MatchingCrysflyWA 870ms41228kbC++112.6kb2023-01-14 15:46:192023-01-14 15:46:23

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:46:23]
  • 评测
  • 测评结果:WA
  • 用时:870ms
  • 内存:41228kb
  • [2023-01-14 15:46:19]
  • 提交

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)