Submission #3228422

---

Source Code Expand

/*#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000005
#define put putchar('\n')
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define go(i,t) for (int i=head[t];i;i=Next[i])
#define sqr(x) ((x)*(x))
#define re register
#define mp make_pair
#define fi first
#define se second
#define pa pair<int,int>
#define pb push_back
#define be begin()
#define en end()
#define ret return puts("IMPOSSIBLE"),0;
#define mod 1000000007
#define N 500055
//#define int ll
using namespace std;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
inline void wr(int x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(int x){wr(x);put;}inline void wri(int x){wr(x);putchar(' ');}
inline void wrn(int x,int y){wri(x);wrn(y);}inline void wrn(int a,int b,int c){wri(a);wrn(b,c);}
int n,m,f[N],vis[N],siz[N],x,cur[N];
int nedge,Next[N*2],head[N],to[N*2];
#define V to[i]
void add(int a,int b){
	Next[++nedge]=head[a];head[a]=nedge;to[nedge]=b;
}
void add_ne(int a,int b){add(a,b);add(b,a);}
inline int ch(int x){
	return x+((x&1)?1:-1);
}
void dfs(int x){
	x=x;
	for(int &i=cur[x];i;i=Next[i]){
		if (vis[ch(i)]) continue;
		vis[i]=1;vis[ch(i)]=1;
		if (V==x+n) f[x]=-1;
		if (V==x-n) f[V]=1;
		dfs(V);
	}
}
signed main(){
	n=read();
	F(i,1,n*2){
		x=read();x=(x==-1)?0:x;
		if (x&&i>n) x+=n;
		add_ne(i,x);siz[x]++;
	}
	F(i,1,n) if ((siz[i]+siz[i+n])%2==1) ret;
	F(i,1,n) if (siz[i]%2==0) add_ne(i,i+n);
	f[0]=-1;F(i,0,n*2) cur[i]=head[i];
	dfs(0);
	//F(i,1,n) if (siz[i]%2==1) f[i]=0;
	puts("POSSIBLE");
	F(i,1,n) wri(f[i]);
	return 0;
}

Submission Info

Judge Result