Submission #6425423

---

Source Code Expand

#include<bits/stdc++.h>
#define next nxt
using namespace std;
int read(){
    int c=0,nx,sign=1;
    do{
        nx=getchar()-'0';
        if(nx=='-'-'0')
            sign=-1;
    }while(nx<0 or nx>9);
    while(nx>=0 and nx<=9){
        c=c*10+nx;
        nx=getchar()-'0';
    }
    return sign*c;
}
const int  N=5e5+100,M=6*N;
int head[N],next[M],ver[M];
inline void addEdge(int u,int v){
    static int now=1;
    ++now;
    next[now]=head[u];
    ver[now]=v;
    head[u]=now;
}
int n;
int cnt[N];
int fa[N],vis[N];
int ans[N];
int main(){
	n=read();
	int u,v,s=2*n+1;
	for(int i=1;i<=n;i++){
		u=read();
		if(u==-1)
			u=s;
		cnt[u]++;
		addEdge(u,i);
		addEdge(i,u);
	}
	for(int i=1;i<=n;i++){
		u=read();
		if(u==-1)
			u=s;
		else
			u=s-u;
		++cnt[u];
		v=s-i;
		addEdge(u,v);
		addEdge(v,u);
	}
	
	for(int i=1;i<=2*n;i++)
		cnt[i]=!(cnt[i]&1);
	cnt[s]=0;
	
	for(int i=1;i<=n;i++){
		if(cnt[i]^cnt[s-i]){
			puts("IMPOSSIBLE");
			return 0;
		}
		if(cnt[i])
			addEdge(i,s-i),addEdge(s-i,i);
	}
	
	u=1;
	while(1){
		int flag=1;
		for(int i=head[u];i;i=next[i]){
			if(vis[i])
				continue;
			v=ver[i];
			flag=0;
			if(v==s-u){
				if(u<=n)
					ans[u]=ans[s-u]=-1;
				else
					ans[u]=ans[s-u]=1;
			}
//			head[u]=next[i];
			vis[i]=vis[i^1]=1;
			u=v;
			break;
		}
		if(flag)
			break;
	}
	
	puts("POSSIBLE");
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]);
}

Submission Info

Judge Result