QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#82242 | #5423. Perfect Matching | Skyjoy | WA | 4ms | 69184kb | C++14 | 2.0kb | 2023-02-27 11:41:53 | 2023-02-27 11:41:55 |
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");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;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 69184kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 3 4 1 2 5 3 6 Yes 2 2 4 3 1 No
result:
wrong answer abs(3-4) != abs(a[3]-a[4]) (test case 1)