QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#82258 | #5423. Perfect Matching | Skyjoy | AC ✓ | 508ms | 82872kb | C++14 | 2.0kb | 2023-02-27 11:51:46 | 2023-02-27 11:51:49 |
Judging History
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)