QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#82227#5423. Perfect MatchingSkyjoyWA 241ms79512kbC++142.0kb2023-02-27 11:31:252023-02-27 11:31:45

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:31:45]
  • 评测
  • 测评结果:WA
  • 用时:241ms
  • 内存:79512kb
  • [2023-02-27 11:31:25]
  • 提交

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)