Submission #1687036
Source Code Expand
#include<iostream> #include<vector> #include<string> #include<algorithm> #include<map> #include<set> #include<utility> #include<cmath> #include<cstring> #include<queue> #include<stack> #include<cstdio> #include<sstream> #include<iomanip> #include<assert.h> #define loop(i,a,b) for(int i=a;i<b;i++) #define rep(i,a) loop(i,0,a) #define pb push_back #define all(in) in.begin(),in.end() #define shosu(x) fixed<<setprecision(x) using namespace std; //kaewasuretyuui typedef long long ll; typedef int Def; typedef pair<Def,Def> pii; typedef vector<Def> vi; typedef vector<vi> vvi; typedef vector<pii> vp; typedef vector<vp> vvp; typedef vector<string> vs; typedef vector<double> vd; typedef vector<vd> vvd; typedef pair<Def,pii> pip; typedef vector<pip>vip; #define mt make_tuple typedef tuple<pii,int,int> tp; typedef vector<tp> vt; template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;} template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;} const double PI=acos(-1); const double EPS=1e-7; Def inf=sizeof(Def)==sizeof(long long)?9e18:1e9; int dx[]={0,1,0,-1,1,1,-1,-1}; int dy[]={1,0,-1,0,1,-1,1,-1}; int n; vi in; vvi G; vi cyc; pii dfs(int a){ vi t; t.pb(inf); rep(i,G[a].size()){ int to=G[a][i]; if(cyc[to])continue; t.pb(dfs(to).first); } sort(all(t)); pii out; int j; rep(i,t.size())if(t[i]!=i){ out.first=i; t.pb(i); j=i; break; } sort(all(t)); loop(i,j,t.size())if(t[i]!=i){ out.second=i; t.pb(i); break; } return out; } int main(){ cin>>n; in=vi(n); rep(i,n)cin>>in[i]; rep(i,n)in[i]--; G=vvi(n); rep(i,n)G[in[i]].pb(i); cyc=vi(n); int t=0; while(cyc[t]==0){ cyc[t]=true; t=in[t]; } cyc=vi(n); while(cyc[t]==0){ cyc[t]=true; t=in[t]; } // rep(i,n)cout<<" "<<cyc[i];cout<<endl; vp num(n,{-1,-1}); rep(i,n)if(cyc[i]){ num[i]=dfs(i); } // rep(i,n)cout<<" "<<num[i].first<<" "<<num[i].second<<endl; rep(i,n)if(cyc[i]){ int t=i; int nu=num[i].first; while(in[t]!=i){ t=in[t]; if(num[t].first==nu)nu=num[t].second; else nu=num[t].first; } if(num[i].first!=nu){ cout<<"POSSIBLE"<<endl; return 0; } t=i;nu=num[i].second; while(in[t]!=i){ t=in[t]; if(num[t].first==nu)nu=num[t].second; else nu=num[t].first; } if(num[i].first==nu){ cout<<"POSSIBLE"<<endl; return 0; } cout<<"IMPOSSIBLE"<<endl; return 0; } }
Submission Info
Submission Time | |
---|---|
Task | F - Namori Grundy |
User | ixmel_rd |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 2523 Byte |
Status | AC |
Exec Time | 121 ms |
Memory | 13184 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 | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
example3 | AC | 1 ms | 256 KB |
loop0 | AC | 105 ms | 10172 KB |
loop1 | AC | 109 ms | 10172 KB |
loop10 | AC | 105 ms | 10172 KB |
loop11 | AC | 102 ms | 10172 KB |
loop12 | AC | 111 ms | 10172 KB |
loop13 | AC | 104 ms | 10176 KB |
loop14 | AC | 104 ms | 10172 KB |
loop15 | AC | 102 ms | 10172 KB |
loop16 | AC | 102 ms | 10172 KB |
loop17 | AC | 107 ms | 10176 KB |
loop18 | AC | 105 ms | 10172 KB |
loop19 | AC | 102 ms | 10176 KB |
loop2 | AC | 105 ms | 10300 KB |
loop3 | AC | 105 ms | 10176 KB |
loop4 | AC | 107 ms | 10172 KB |
loop5 | AC | 104 ms | 10172 KB |
loop6 | AC | 104 ms | 10300 KB |
loop7 | AC | 104 ms | 10176 KB |
loop8 | AC | 104 ms | 10176 KB |
loop9 | AC | 105 ms | 10176 KB |
loopex0 | AC | 107 ms | 10416 KB |
loopex1 | AC | 104 ms | 10296 KB |
loopex10 | AC | 105 ms | 10176 KB |
loopex11 | AC | 105 ms | 10300 KB |
loopex12 | AC | 113 ms | 10172 KB |
loopex13 | AC | 104 ms | 10172 KB |
loopex14 | AC | 105 ms | 10176 KB |
loopex15 | AC | 105 ms | 10300 KB |
loopex16 | AC | 106 ms | 10416 KB |
loopex17 | AC | 107 ms | 10300 KB |
loopex18 | AC | 108 ms | 10532 KB |
loopex19 | AC | 104 ms | 10176 KB |
loopex2 | AC | 104 ms | 10176 KB |
loopex20 | AC | 104 ms | 10176 KB |
loopex21 | AC | 106 ms | 10416 KB |
loopex22 | AC | 111 ms | 10416 KB |
loopex23 | AC | 106 ms | 10172 KB |
loopex3 | AC | 112 ms | 10176 KB |
loopex4 | AC | 104 ms | 10172 KB |
loopex5 | AC | 107 ms | 10412 KB |
loopex6 | AC | 104 ms | 10176 KB |
loopex7 | AC | 108 ms | 10296 KB |
loopex8 | AC | 106 ms | 10292 KB |
loopex9 | AC | 107 ms | 10412 KB |
rand0 | AC | 32 ms | 3248 KB |
rand1 | AC | 47 ms | 4680 KB |
rand2 | AC | 12 ms | 1664 KB |
rand3 | AC | 94 ms | 9120 KB |
rand4 | AC | 121 ms | 13184 KB |
rand5 | AC | 54 ms | 5400 KB |
rand6 | AC | 22 ms | 2540 KB |
rand7 | AC | 6 ms | 896 KB |
rand8 | AC | 80 ms | 7692 KB |
rand9 | AC | 5 ms | 768 KB |
small0 | AC | 1 ms | 256 KB |
small1 | AC | 1 ms | 256 KB |
small2 | AC | 1 ms | 256 KB |
small3 | AC | 1 ms | 256 KB |
small4 | AC | 1 ms | 256 KB |
small5 | AC | 1 ms | 256 KB |
small6 | AC | 1 ms | 256 KB |
small7 | AC | 1 ms | 256 KB |
small8 | AC | 1 ms | 256 KB |
small9 | AC | 1 ms | 256 KB |