QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#82242#5423. Perfect MatchingSkyjoyWA 4ms69184kbC++142.0kb2023-02-27 11:41:532023-02-27 11:41:55

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:41:55]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:69184kb
  • [2023-02-27 11:41:53]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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)