QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#82238#5423. Perfect MatchingSkyjoyRE 8ms69156kbC++142.0kb2023-02-27 11:38:182023-02-27 11:38:42

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:38:42]
  • 评测
  • 测评结果:RE
  • 用时:8ms
  • 内存:69156kb
  • [2023-02-27 11:38:18]
  • 提交

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");
		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: 69156kb

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:


result: