Submission #1688315


Source Code Expand

///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
//                       _oo0oo_                         //
//                      o8888888o                        //
//                      88" . "88      ------ hzt1       //
//                      (| -_- |)                        //
//                      0\  =  /0                        //
//                    ___/`---'\___                      //
//                  .' \|     |// '.                     //
//                 / \|||  :  |||// \                    //
//                / _||||| -:- |||||- \                  //
//               |   | \  -  /// |     |                 //
//               | \_|  ''\---/''  |_/ |                 //
//               \  .-\__  '-'  ___/-. /                 //
//             ___'. .'  /--.--\  `. .'___               //
//          ."" '<  `.___\_<|>_/___.' >' "".             //
//         | | :  `- \`.;`\ _ /`;.`/ - ` : | |           //
//         \  \ `_.   \_ __\ /__ _/   .-` /  /           //
//     =====`-.____`.___ \_____/___.-`___.-'=====        //
//                       `=---='                         //
//                                                       //
//                                                       //
//     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~       //
//                                                       //
//                 God-He Bless All.                     //
//           This Code Will Never Explode.               //
//                                                       //
//                                                       //
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>
#define rep(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;i++)
#define dwn(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;i--)
using namespace std;
const int Size=1<<16;
char buffer[Size],*head,*tail;
inline char Getchar() {
    if(head==tail) {
        int l=fread(buffer,1,Size,stdin);
        tail=(head=buffer)+l;
    }
    if(head==tail) return -1;
    return *head++;
}
inline int read() {
    int x=0,f=1;char c=Getchar();
    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
    return x*f;
}
typedef long long ll;
const int maxn=200010;
vector<int>G[maxn];
int n,p[maxn],vis[maxn],A[maxn],B[maxn],in[maxn],first[maxn],nxt[maxn],to[maxn],e;
void AddEdge(int u,int v) {G[v].push_back(u);in[v]++;to[++e]=v;nxt[e]=first[u];first[u]=e;}
int Q[maxn],S[maxn];
int work(int x) {
	memset(S,0,sizeof(S));
	int y=x;
	do {
		y=p[y];
		rep(i,0,G[y].size()-1) S[B[G[y][i]]]++;
		rep(i,0,3) if(!S[i]) {B[y]=i;break;}
		rep(i,0,3) S[i]=0;
	}while(y!=x);
	rep(x,1,n) {
		rep(i,0,G[x].size()-1) S[B[G[x][i]]]++;
		rep(i,0,3) if(!S[i]) {if(i!=B[x]) return 0;break;}
		rep(i,0,3) S[i]=0;
	}
//	rep(i,1,n) printf("%d%c",B[i],i==n?'\n':' ');
	return 1;
}
int solve() {
	memset(A,-1,sizeof(A));
	int l=1,r=0;
	rep(i,1,n) if(!in[i]) Q[++r]=i,A[i]=0;
	while(l<=r) {
		int x=Q[l++];vis[x]=1;
		for(int i=first[x];i;i=nxt[i]) if(!(--in[to[i]])) Q[++r]=to[i],A[to[i]]=A[x]^1;
	}
	rep(i,1,n) if(!vis[i]) {
		rep(j,1,n) B[j]=A[j];
		B[i]=0;if(work(i)) return 1;
		rep(j,1,n) B[j]=A[j];
		B[i]=1;if(work(i)) return 1;
		rep(j,1,n) B[j]=A[j];
		B[i]=2;if(work(i)) return 1;
		rep(j,1,n) B[j]=A[j];
		B[i]=3;if(work(i)) return 1;
	}
}
int main() {
	n=read();
	rep(i,1,n) AddEdge(i,p[i]=read());
	puts(solve()?"POSSIBLE":"IMPOSSIBLE");
	return 0;
}

Submission Info

Submission Time
Task F - Namori Grundy
User wzj52501
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3759 Byte
Status WA
Exec Time 2108 ms
Memory 17408 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 4
AC × 42
WA × 17
TLE × 9
Set Name Test Cases
Sample example0, example1, example2, example3
All example0, example1, example2, example3, loop0, loop1, loop10, loop11, loop12, loop13, loop14, loop15, loop16, loop17, loop18, loop19, loop2, loop3, loop4, loop5, loop6, loop7, loop8, loop9, loopex0, loopex1, loopex10, loopex11, loopex12, loopex13, loopex14, loopex15, loopex16, loopex17, loopex18, loopex19, loopex2, loopex20, loopex21, loopex22, loopex23, loopex3, loopex4, loopex5, loopex6, loopex7, loopex8, loopex9, rand0, rand1, rand2, rand3, rand4, rand5, rand6, rand7, rand8, rand9, small0, small1, small2, small3, small4, small5, small6, small7, small8, small9
Case Name Status Exec Time Memory
example0 AC 4 ms 11520 KB
example1 AC 5 ms 11520 KB
example2 AC 4 ms 11520 KB
example3 AC 5 ms 11520 KB
loop0 WA 1045 ms 15616 KB
loop1 WA 909 ms 15616 KB
loop10 WA 1501 ms 15616 KB
loop11 WA 1121 ms 15616 KB
loop12 WA 1125 ms 15616 KB
loop13 WA 1427 ms 15616 KB
loop14 WA 974 ms 15616 KB
loop15 WA 1110 ms 15616 KB
loop16 WA 1468 ms 15616 KB
loop17 WA 1096 ms 15616 KB
loop18 AC 1037 ms 15616 KB
loop19 AC 1232 ms 15616 KB
loop2 WA 1399 ms 15616 KB
loop3 WA 1214 ms 15616 KB
loop4 WA 1268 ms 15616 KB
loop5 WA 970 ms 15616 KB
loop6 WA 1384 ms 15616 KB
loop7 WA 1417 ms 15616 KB
loop8 AC 1569 ms 15616 KB
loop9 AC 936 ms 15616 KB
loopex0 AC 662 ms 15744 KB
loopex1 AC 331 ms 15616 KB
loopex10 AC 513 ms 15616 KB
loopex11 WA 143 ms 15616 KB
loopex12 AC 345 ms 15616 KB
loopex13 AC 459 ms 15616 KB
loopex14 AC 503 ms 15616 KB
loopex15 AC 573 ms 15616 KB
loopex16 AC 348 ms 15744 KB
loopex17 AC 511 ms 15616 KB
loopex18 AC 515 ms 15744 KB
loopex19 AC 607 ms 15616 KB
loopex2 AC 546 ms 15616 KB
loopex20 AC 550 ms 15616 KB
loopex21 AC 486 ms 15744 KB
loopex22 AC 527 ms 15744 KB
loopex23 AC 464 ms 15616 KB
loopex3 AC 457 ms 15616 KB
loopex4 AC 635 ms 15616 KB
loopex5 AC 481 ms 15744 KB
loopex6 AC 141 ms 15616 KB
loopex7 AC 465 ms 15616 KB
loopex8 AC 443 ms 15744 KB
loopex9 AC 641 ms 15744 KB
rand0 TLE 2103 ms 12800 KB
rand1 TLE 2103 ms 13440 KB
rand2 AC 6 ms 12160 KB
rand3 TLE 2104 ms 15232 KB
rand4 TLE 2108 ms 17408 KB
rand5 TLE 2103 ms 13696 KB
rand6 TLE 2103 ms 12544 KB
rand7 TLE 2103 ms 11776 KB
rand8 TLE 2104 ms 14720 KB
rand9 TLE 2103 ms 11776 KB
small0 AC 4 ms 11520 KB
small1 AC 4 ms 11520 KB
small2 AC 4 ms 11520 KB
small3 AC 4 ms 11520 KB
small4 AC 5 ms 11520 KB
small5 AC 4 ms 11520 KB
small6 AC 4 ms 11520 KB
small7 AC 4 ms 11520 KB
small8 AC 4 ms 11520 KB
small9 AC 4 ms 11520 KB