QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#82227 | #5423. Perfect Matching | Skyjoy | WA | 241ms | 79512kb | C++14 | 2.0kb | 2023-02-27 11:31:25 | 2023-02-27 11:31:45 |
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])if(dfs(v,u,i>>1))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: 69184kb
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: -100
Wrong Answer
time: 241ms
memory: 79512kb
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 86 44 146 104 206 188 383 344 392 386 476 404 542 482 638 626 848 758 881 854 1073 920 1109 1094 1229 1184 1280 1250 1376 1295 1415 1412 1532 1505 1547 1544 1679 1607 1784 1742 1877 1829 1955 1907 2096 1982 2210 2201 2291 2264 2405 2339 2540 2450 2603 2588 2738 2639 2858 2768 2975 2906 3053 2987...
result:
wrong output format Expected integer, but "Yes" found (test case 1)