QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#82244 | #5423. Perfect Matching | Skyjoy | RE | 8ms | 69040kb | C++14 | 2.0kb | 2023-02-27 11:42:42 | 2023-02-27 11:42:44 |
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");
if(ans.size()!=n/2)cout<<ans.size()<<endl;
assert(ans.size()==n/2);
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: 8ms
memory: 69040kb
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
Dangerous Syscalls
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 33320