QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#82258#5423. Perfect MatchingSkyjoyAC ✓508ms82872kbC++142.0kb2023-02-27 11:51:462023-02-27 11:51:49

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-27 11:51:49]
  • 评测
  • 测评结果:AC
  • 用时:508ms
  • 内存:82872kb
  • [2023-02-27 11:51:46]
  • 提交

answer

#include<bits/stdc++.h>
#define I using
#define love namespace
#define Elaina std
I love Elaina;
const int N=1000010;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int T,n,m,k,a[N],b[N],c[N],p[N],q[N],head[N<<1],cnt,x,y,fi[N<<1],siz[N<<1],dep[N<<1];
bool flag;
vector<int>qwq[N<<1];
vector<pair<int,int> >ans;
int find(int x){return x==fi[x]?x:fi[x]=find(fi[x]);}
struct edge{int to,nxt;}e[N<<1];
void addedge(int u,int v){e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;}
bool dfs(int u,int fa,int last){
	qwq[u].clear();
	dep[u]=dep[fa]+1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)continue;
		if(!dep[v]){
			bool tmp=dfs(v,u,i>>1);
			if(tmp)qwq[u].push_back(i>>1);
		}
		else if(dep[v]<dep[u])qwq[u].push_back(i>>1);
	}
	while(qwq[u].size()>1)ans.push_back(make_pair(qwq[u][qwq[u].size()-2],qwq[u][qwq[u].size()-1])),qwq[u].pop_back(),qwq[u].pop_back();
	if(qwq[u].empty())return 1;
	else{
		ans.push_back(make_pair(qwq[u].back(),last));
		return 0;
	}
}
int main(){
	T=read();
	while(T--){
		flag=cnt=1;
		ans.clear();
		n=read();
		for(int i=1;i<=n;i++)a[i]=read(),b[i]=p[i]=a[i]-i,c[i]=q[i]=a[i]+i;
		sort(p+1,p+n+1),sort(q+1,q+n+1);
		m=unique(p+1,p+n+1)-p-1,k=unique(q+1,q+n+1)-q-1;
		for(int i=1;i<=m+k;i++)head[i]=siz[i]=dep[i]=0,fi[i]=i;
		for(int i=1;i<=n;i++){
			b[i]=lower_bound(p+1,p+m+1,b[i])-p,c[i]=lower_bound(q+1,q+k+1,c[i])-q;
			addedge(b[i],c[i]+m),addedge(c[i]+m,b[i]);
			x=find(b[i]),y=find(c[i]+m);
			if(x==y){
				siz[x]++;
				continue;
			}
			fi[x]=y;
			siz[y]+=siz[x]+1;
		}
		for(int i=1;i<=m+k;i++){
			if(i!=fi[i])continue;
			if(siz[i]&1){
				puts("No");
				flag=0;
				break;
			}
			dfs(i,0,0);
		}
		if(!flag)continue;
		puts("Yes");
		for(pair<int,int>tmp:ans)printf("%d %d\n",tmp.first,tmp.second);
	}
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 69068kb

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
2 4
3 1
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: 0
Accepted
time: 303ms
memory: 82872kb

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
99977 99979
99821 99823
99980 99981
99929 99930
99994 99993
99940 99939
99928 99927
99894 99893
99892 99891
99873 99872
99985 99983
99937 99935
99925 99923
99814 99812
99796 99795
99772 99771
99727 99725
99724 99723
99706 99704
99700 99699
99673 99671
99640 99638
99628 99627
99586 99584
99550 99...

result:

ok 10 Cases (10 test cases)

Test #3:

score: 0
Accepted
time: 4ms
memory: 68960kb

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
40 39
42 41
44 43
46 45
48 47
50 49
52 51
54 53
56 55
57 58
30 29
32 31
34 33
76 75
78 77
80 79
82 81
84 83
86 85
88 87
90 89
92 91
94 93
96 95
98 97
100 99
10 9
12 11
14 13
16 15
18 17
20 19
22 21
24 23
26 25
28 27
60 59
62 61
64 63
66 65
68 67
36 35
37 38
2 1
4 3
6 5
7 8
70 69
72 71
74 73
Yes
...

result:

ok 10 Cases (10 test cases)

Test #4:

score: 0
Accepted
time: 223ms
memory: 81856kb

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
29330 29329
29332 29331
29334 29333
29336 29335
29338 29337
29340 29339
29342 29341
29344 29343
29346 29345
29348 29347
29350 29349
29352 29351
71754 71753
71756 71755
71758 71757
71760 71759
71762 71761
71764 71763
71766 71765
71768 71767
71770 71769
71772 71771
71774 71773
71776 71775
71778 71...

result:

ok 10 Cases (10 test cases)

Test #5:

score: 0
Accepted
time: 508ms
memory: 77940kb

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
25729 25177
96172 81564
82692 81449
87276 72615
89930 51424
90797 40204
84293 82260
81601 68474
63426 23563
81768 79940
89209 65068
78623 77535
71925 42616
50015 45416
63727 61582
94113 64578
71688 55765
87755 74925
86349 67712
97794 89613
98375 83954
85705 76781
96630 92136
62221 59568
77914 65...

result:

ok 10 Cases (10 test cases)

Test #6:

score: 0
Accepted
time: 153ms
memory: 69028kb

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
987 986
963 962
952 951
913 912
858 857
771 770
740 739
728 727
721 720
719 718
705 704
700 699
664 663
600 599
584 583
503 502
456 455
444 443
418 417
407 406
405 404
343 342
319 318
310 309
263 262
261 260
211 210
193 192
180 179
156 155
148 147
128 127
108 107
73 72
48 47
34...

result:

ok 1000 Cases (1000 test cases)