Submission #5475398
Source Code Expand
#include <bits/stdc++.h> #define For(i, l, r) for (register int i = (l), i##end = int(r); i <= i##end; ++i) #define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i) #define Rep(i, r) for (register int i = (0), i##end = int(r); i < i##end; ++i) #define Set(a, v) memset(a, v, sizeof(a)) #define Cpy(a, b) memcpy(a, b, sizeof(a)) #define debug(x) cout << #x << ": " << (x) << endl using namespace std; template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; } inline int read() { int x(0), sgn(1); char ch(getchar()); for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1; for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48); return x * sgn; } void File() { #ifdef zjp_shadow freopen ("F.in", "r", stdin); freopen ("F.out", "w", stdout); #endif } const int N = 2e5 + 1e3; vector<int> G[N]; int mex[N], n, p[N]; bool vis[N], cir[N], app[N]; void Dfs(int u) { for (int v : G[u]) if (!cir[v]) Dfs(v); for (int v : G[u]) if (!cir[v]) app[mex[v]] = true; while (app[mex[u]]) ++ mex[u]; for (int v : G[u]) app[mex[v]] = false; } int main () { File(); n = read(); For (i, 1, n) G[p[i] = read()].push_back(i); int x = 1; for (; !vis[x]; x = p[x]) vis[x] = true; for (; !cir[x]; x = p[x]) cir[x] = true; int minv = n + 1, maxv = 0, cnt = 0; For (i, 1, n) if (cir[i]) Dfs(i), ++ cnt, chkmax(maxv, mex[i]), chkmin(minv, mex[i]); puts(maxv == minv && (cnt & 1) ? "IMPOSSIBLE" : "POSSIBLE"); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Namori Grundy |
User | zjp_shadow |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1650 Byte |
Status | AC |
Exec Time | 42 ms |
Memory | 12160 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 800 | ||||
Status |
|
|
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 | 3 ms | 5120 KB |
example1 | AC | 3 ms | 5120 KB |
example2 | AC | 3 ms | 5120 KB |
example3 | AC | 3 ms | 5120 KB |
loop0 | AC | 31 ms | 9728 KB |
loop1 | AC | 31 ms | 9728 KB |
loop10 | AC | 32 ms | 9728 KB |
loop11 | AC | 34 ms | 9728 KB |
loop12 | AC | 31 ms | 9728 KB |
loop13 | AC | 32 ms | 9728 KB |
loop14 | AC | 30 ms | 9728 KB |
loop15 | AC | 31 ms | 9728 KB |
loop16 | AC | 36 ms | 9728 KB |
loop17 | AC | 30 ms | 9728 KB |
loop18 | AC | 32 ms | 9728 KB |
loop19 | AC | 30 ms | 9728 KB |
loop2 | AC | 30 ms | 9728 KB |
loop3 | AC | 31 ms | 9728 KB |
loop4 | AC | 31 ms | 9728 KB |
loop5 | AC | 31 ms | 9728 KB |
loop6 | AC | 32 ms | 9728 KB |
loop7 | AC | 30 ms | 9728 KB |
loop8 | AC | 31 ms | 9728 KB |
loop9 | AC | 30 ms | 9728 KB |
loopex0 | AC | 32 ms | 9856 KB |
loopex1 | AC | 30 ms | 9728 KB |
loopex10 | AC | 32 ms | 9728 KB |
loopex11 | AC | 30 ms | 9728 KB |
loopex12 | AC | 31 ms | 9728 KB |
loopex13 | AC | 31 ms | 9728 KB |
loopex14 | AC | 31 ms | 9728 KB |
loopex15 | AC | 31 ms | 9728 KB |
loopex16 | AC | 32 ms | 9856 KB |
loopex17 | AC | 30 ms | 9728 KB |
loopex18 | AC | 31 ms | 9856 KB |
loopex19 | AC | 31 ms | 9728 KB |
loopex2 | AC | 31 ms | 9728 KB |
loopex20 | AC | 31 ms | 9728 KB |
loopex21 | AC | 31 ms | 9856 KB |
loopex22 | AC | 31 ms | 9856 KB |
loopex23 | AC | 30 ms | 9728 KB |
loopex3 | AC | 32 ms | 9728 KB |
loopex4 | AC | 30 ms | 9728 KB |
loopex5 | AC | 31 ms | 9856 KB |
loopex6 | AC | 30 ms | 9728 KB |
loopex7 | AC | 32 ms | 9728 KB |
loopex8 | AC | 31 ms | 9728 KB |
loopex9 | AC | 32 ms | 9856 KB |
rand0 | AC | 11 ms | 6528 KB |
rand1 | AC | 15 ms | 7296 KB |
rand2 | AC | 5 ms | 5888 KB |
rand3 | AC | 29 ms | 9472 KB |
rand4 | AC | 42 ms | 12160 KB |
rand5 | AC | 17 ms | 7552 KB |
rand6 | AC | 8 ms | 6272 KB |
rand7 | AC | 4 ms | 5376 KB |
rand8 | AC | 24 ms | 8832 KB |
rand9 | AC | 4 ms | 5376 KB |
small0 | AC | 3 ms | 5120 KB |
small1 | AC | 3 ms | 5120 KB |
small2 | AC | 3 ms | 5120 KB |
small3 | AC | 3 ms | 5120 KB |
small4 | AC | 3 ms | 5120 KB |
small5 | AC | 3 ms | 5120 KB |
small6 | AC | 3 ms | 5120 KB |
small7 | AC | 3 ms | 5120 KB |
small8 | AC | 3 ms | 5120 KB |
small9 | AC | 3 ms | 5120 KB |