Submission #1476760


Source Code Expand

Copy
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;

#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mt make_tuple
#define mp make_pair
#define ZERO(a) memset(a,0,sizeof(a))
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
#define exists find_if
#define forall all_of

using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;
using ld = long double;  using vld = vector<ld>; 
using vi = vector<int>; using vvi = vector<vi>; vll conv(vi& v) { vll r(v.size()); rep(i, v.size()) r[i] = v[i]; return r; }
using Pos = complex<double>;

template <typename T, typename U> ostream &operator<<(ostream &o, const pair<T, U> &v) {  o << "(" << v.first << ", " << v.second << ")"; return o; }
template<size_t...> struct seq{}; template<size_t N, size_t... Is> struct gen_seq : gen_seq<N-1, N-1, Is...>{}; template<size_t... Is> struct gen_seq<0, Is...> : seq<Is...>{};
template<class Ch, class Tr, class Tuple, size_t... Is>
void print_tuple(basic_ostream<Ch,Tr>& os, Tuple const& t, seq<Is...>){ using s = int[]; (void)s{0, (void(os << (Is == 0? "" : ", ") << get<Is>(t)), 0)...}; }
template<class Ch, class Tr, class... Args> 
auto operator<<(basic_ostream<Ch, Tr>& os, tuple<Args...> const& t) -> basic_ostream<Ch, Tr>& { os << "("; print_tuple(os, t, gen_seq<sizeof...(Args)>()); return os << ")"; }
ostream &operator<<(ostream &o, const vvll &v) { rep(i, v.size()) { rep(j, v[i].size()) o << v[i][j] << " "; o << endl; } return o; }
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]";  return o; }
template <typename T>  ostream &operator<<(ostream &o, const set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T>  ostream &operator<<(ostream &o, const unordered_set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U>  ostream &operator<<(ostream &o, const map<T, U> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U, typename V>  ostream &operator<<(ostream &o, const unordered_map<T, U, V> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it; o << "]";  return o; }
vector<int> range(const int x, const int y) { vector<int> v(y - x + 1); iota(v.begin(), v.end(), x); return v; }
template <typename T> istream& operator>>(istream& i, vector<T>& o) { rep(j, o.size()) i >> o[j]; return i;}
string bits_to_string(ll input, ll n=64) { string s; rep(i, n) s += '0' + !!(input & (1ll << i)); reverse(all(s)); return s; }

template <typename T> unordered_map<T, ll> counter(vector<T> vec){unordered_map<T, ll> ret; for (auto&& x : vec) ret[x]++; return ret;};
string substr(string s, P x) {return s.substr(x.fi, x.se - x.fi); }
struct ci : public iterator<forward_iterator_tag, ll> { ll n; ci(const ll n) : n(n) { } bool operator==(const ci& x) { return n == x.n; } bool operator!=(const ci& x) { return !(*this == x); } ci &operator++() { n++; return *this; } ll operator*() const { return n; } };

size_t random_seed; namespace std { using argument_type = P; template<> struct hash<argument_type> { size_t operator()(argument_type const& x) const { size_t seed = random_seed; seed ^= hash<ll>{}(x.fi); seed ^= (hash<ll>{}(x.se) << 1); return seed; } }; }; // hash for various class
namespace myhash{ const int Bsizes[]={3,9,13,17,21,25,29,33,37,41,45,49,53,57,61,65,69,73,77,81}; const int xor_nums[]={0x100007d1,0x5ff049c9,0x14560859,0x07087fef,0x3e277d49,0x4dba1f17,0x709c5988,0x05904258,0x1aa71872,0x238819b3,0x7b002bb7,0x1cf91302,0x0012290a,0x1083576b,0x76473e49,0x3d86295b,0x20536814,0x08634f4d,0x115405e8,0x0e6359f2}; const int hash_key=xor_nums[rand()%20]; const int mod_key=xor_nums[rand()%20]; template <typename T> struct myhash{ std::size_t operator()(const T& val) const { return (hash<T>{}(val)%mod_key)^hash_key; } }; };
template <typename T> class uset:public std::unordered_set<T,myhash::myhash<T>> { using SET=std::unordered_set<T,myhash::myhash<T>>; public: uset():SET(){SET::rehash(myhash::Bsizes[rand()%20]);} };
template <typename T,typename U> class umap:public std::unordered_map<T,U,myhash::myhash<T>> { public: using MAP=std::unordered_map<T,U,myhash::myhash<T>>; umap():MAP(){MAP::rehash(myhash::Bsizes[rand()%20]);} };    

struct timeval start; double sec() { struct timeval tv; gettimeofday(&tv, NULL); return (tv.tv_sec - start.tv_sec) + (tv.tv_usec - start.tv_usec) * 1e-6; }
struct init_{init_(){ gettimeofday(&start, NULL); ios::sync_with_stdio(false); cin.tie(0); srand((unsigned int)time(NULL)); random_seed = RAND_MAX / 2 + rand() / 2; }} init__;

static const double EPS = 1e-14;
static const long long INF = 1e18;
static const long long mo = 1e9+7;
#define ldout fixed << setprecision(40) 

vvll g, gr;

vll order;
ll order_counter = 0;
void scc_for(ll v) {
    if (order[v] >= 0) return;
    order[v] = INF;
    for (auto u : g[v]) {
        scc_for(u);
    }
    order[v] = order_counter++;
}
vvll scc_set;
vector<bool> flag;
void scc_rev(ll i, ll v) {
    if (flag[v]) return;
    flag[v] = 1;
    scc_set[i].pb(v);
    for (auto u : gr[v]) {
        scc_rev(i, u);
    }
}
vvll getSCC(void) {
    ll n = g.size();

    order.resize(n, -1);
    order_counter = 0;
    scc_set.clear();
    flag.resize(n);

    rep(v, g.size()) {
        scc_for(v);
    }
    vll order_rev(n);
    rep(i, n) {
        order_rev[n-1-order[i]] = i;
    }
    rep(i, g.size()) {
        ll v = order_rev[i];
        if (!flag[v]) {
            scc_set.pb({});
            scc_rev(scc_set.size()-1, v);
        }
    }
    return scc_set;
}
unordered_set<ll> cycle;
vll grundy;
ll grundy_dfs(ll v) {
    if (cycle.count(v)) {
        return -1;
    }
    if (grundy[v] >= 0) {
        return grundy[v];
    }
    if (g[v].size() == 0) {
        return grundy[v] = 0;
    }

    unordered_set<ll> memo;
    for (auto&& u : g[v]) {
        memo.insert(grundy_dfs(u));
    }
    rep(i, INF) {
        if (!memo.count(i)) {
            return grundy[v] = i;
        }
    }
    assert(0);
    return -1;
}


int main(void) {
    ll n; cin >> n;
    vll a(n); cin >> a;
    g.resize(n), gr.resize(n);
    rep(i, n) {
        g [a[i]-1].pb(i);
        gr[i].pb(a[i]-1);
    }

    vvll scc = getSCC();
//    cout << scc << endl;

    for (auto&& vv : scc) {
        if (vv.size() > 1) {
            for (auto&& v : vv) {
                cycle.insert(v);
            }
        }
    }
    if (cycle.empty()) {
        cout << "POSSIBLE" << endl;
        return 0;
    }

    grundy = vll(n, -1);
    rep(i, n) if (!cycle.count(i)) {
        grundy_dfs(i);
    }
//    cout << grundy << endl;

    ll v = *cycle.begin();
    unordered_set<ll> memo;
    for (auto u : g[v]) {
        memo.insert(grundy[u]);
    }
    cycle = {};
    ll counter = 2;
    rep(i, INF) {
        if (!counter) break;
        if (!memo.count(i)) {
//            cout << i << "#CAND" << endl;
            auto backup = grundy;
            grundy[v] = i;
            rep(i, n) {
                grundy_dfs(i);
            }
//            cout << grundy << endl;
            rep(i, n) {
//                cout << i <<"###########"<< endl;
                assert(grundy[i] != -1);
                unordered_set<ll> memo;
                for (auto&& u : g[i]) {
//                    cout << u << " : "<< grundy[u]<< endl;
                    memo.insert(grundy[u]);
                }
                ll grundy_i = -1;
                rep(i, INF) {
                    if (!memo.count(i)) {
                        grundy_i = i;
                        break;
                    }
                }
                if (grundy[i] != grundy_i) {
//                    cout << i << " " << grundy[i] << " : " << memo << endl;
                    goto SKIP;
                }
            }
            cout << "POSSIBLE" << endl;
            return 0;
            SKIP:;
            grundy = backup;
            counter--;
        }
    }
    cout << "IMPOSSIBLE" << endl;

    return 0;
}

Submission Info

Submission Time
Task F - Namori Grundy
User hamko
Language C++14 (GCC 5.4.1)
Score 800
Code Size 8813 Byte
Status
Exec Time 293 ms
Memory 48372 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0, example1, example2, example3
All 800 / 800 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 1 ms 256 KB
example1 1 ms 256 KB
example2 1 ms 256 KB
example3 1 ms 256 KB
loop0 181 ms 44200 KB
loop1 198 ms 43176 KB
loop10 212 ms 44328 KB
loop11 205 ms 44968 KB
loop12 192 ms 45096 KB
loop13 197 ms 43180 KB
loop14 157 ms 45096 KB
loop15 175 ms 44072 KB
loop16 168 ms 43560 KB
loop17 184 ms 43820 KB
loop18 185 ms 44840 KB
loop19 178 ms 43436 KB
loop2 153 ms 43304 KB
loop3 159 ms 44332 KB
loop4 174 ms 44968 KB
loop5 174 ms 44712 KB
loop6 187 ms 43816 KB
loop7 212 ms 44204 KB
loop8 180 ms 43692 KB
loop9 176 ms 44460 KB
loopex0 204 ms 44044 KB
loopex1 198 ms 43808 KB
loopex10 176 ms 44076 KB
loopex11 161 ms 43684 KB
loopex12 188 ms 44328 KB
loopex13 192 ms 44456 KB
loopex14 200 ms 44588 KB
loopex15 178 ms 43428 KB
loopex16 181 ms 45324 KB
loopex17 209 ms 44580 KB
loopex18 187 ms 45432 KB
loopex19 185 ms 44716 KB
loopex2 193 ms 43180 KB
loopex20 186 ms 43436 KB
loopex21 186 ms 44304 KB
loopex22 208 ms 45200 KB
loopex23 201 ms 44072 KB
loopex3 190 ms 43308 KB
loopex4 210 ms 44072 KB
loopex5 201 ms 44548 KB
loopex6 180 ms 43692 KB
loopex7 198 ms 44060 KB
loopex8 206 ms 44440 KB
loopex9 208 ms 44552 KB
rand0 56 ms 13080 KB
rand1 71 ms 19140 KB
rand2 23 ms 5348 KB
rand3 151 ms 37676 KB
rand4 293 ms 48372 KB
rand5 85 ms 23516 KB
rand6 34 ms 9752 KB
rand7 9 ms 2688 KB
rand8 122 ms 33036 KB
rand9 8 ms 2432 KB
small0 1 ms 256 KB
small1 1 ms 256 KB
small2 1 ms 256 KB
small3 1 ms 256 KB
small4 1 ms 256 KB
small5 1 ms 256 KB
small6 1 ms 256 KB
small7 1 ms 256 KB
small8 1 ms 256 KB
small9 1 ms 256 KB