結果
問題 | No.1013 〇マス進む |
ユーザー | otamay6 |
提出日時 | 2019-11-09 14:07:41 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 195 ms / 2,000 ms |
コード長 | 5,411 bytes |
コンパイル時間 | 2,977 ms |
コンパイル使用メモリ | 194,276 KB |
実行使用メモリ | 14,068 KB |
最終ジャッジ日時 | 2023-10-13 07:09:18 |
合計ジャッジ時間 | 12,020 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,352 KB |
testcase_02 | AC | 1 ms
4,352 KB |
testcase_03 | AC | 2 ms
4,352 KB |
testcase_04 | AC | 2 ms
4,352 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,352 KB |
testcase_07 | AC | 3 ms
4,348 KB |
testcase_08 | AC | 2 ms
4,352 KB |
testcase_09 | AC | 3 ms
4,348 KB |
testcase_10 | AC | 3 ms
4,352 KB |
testcase_11 | AC | 2 ms
4,348 KB |
testcase_12 | AC | 3 ms
4,348 KB |
testcase_13 | AC | 8 ms
4,348 KB |
testcase_14 | AC | 89 ms
8,396 KB |
testcase_15 | AC | 145 ms
11,444 KB |
testcase_16 | AC | 136 ms
10,868 KB |
testcase_17 | AC | 78 ms
7,600 KB |
testcase_18 | AC | 99 ms
8,692 KB |
testcase_19 | AC | 57 ms
6,444 KB |
testcase_20 | AC | 185 ms
13,440 KB |
testcase_21 | AC | 71 ms
7,236 KB |
testcase_22 | AC | 99 ms
8,944 KB |
testcase_23 | AC | 32 ms
5,020 KB |
testcase_24 | AC | 191 ms
13,748 KB |
testcase_25 | AC | 181 ms
13,484 KB |
testcase_26 | AC | 33 ms
4,944 KB |
testcase_27 | AC | 68 ms
7,080 KB |
testcase_28 | AC | 33 ms
4,984 KB |
testcase_29 | AC | 180 ms
13,112 KB |
testcase_30 | AC | 61 ms
6,628 KB |
testcase_31 | AC | 118 ms
9,804 KB |
testcase_32 | AC | 87 ms
8,112 KB |
testcase_33 | AC | 87 ms
8,376 KB |
testcase_34 | AC | 140 ms
10,964 KB |
testcase_35 | AC | 132 ms
10,528 KB |
testcase_36 | AC | 10 ms
4,356 KB |
testcase_37 | AC | 10 ms
4,348 KB |
testcase_38 | AC | 153 ms
11,768 KB |
testcase_39 | AC | 48 ms
5,964 KB |
testcase_40 | AC | 140 ms
10,984 KB |
testcase_41 | AC | 34 ms
5,012 KB |
testcase_42 | AC | 81 ms
7,948 KB |
testcase_43 | AC | 53 ms
6,128 KB |
testcase_44 | AC | 88 ms
8,096 KB |
testcase_45 | AC | 78 ms
7,608 KB |
testcase_46 | AC | 36 ms
5,252 KB |
testcase_47 | AC | 83 ms
7,960 KB |
testcase_48 | AC | 98 ms
8,736 KB |
testcase_49 | AC | 138 ms
11,216 KB |
testcase_50 | AC | 117 ms
9,864 KB |
testcase_51 | AC | 106 ms
9,060 KB |
testcase_52 | AC | 19 ms
4,592 KB |
testcase_53 | AC | 30 ms
4,588 KB |
testcase_54 | AC | 132 ms
10,624 KB |
testcase_55 | AC | 39 ms
5,344 KB |
testcase_56 | AC | 166 ms
12,464 KB |
testcase_57 | AC | 111 ms
9,576 KB |
testcase_58 | AC | 187 ms
13,976 KB |
testcase_59 | AC | 190 ms
14,068 KB |
testcase_60 | AC | 187 ms
13,924 KB |
testcase_61 | AC | 188 ms
13,864 KB |
testcase_62 | AC | 195 ms
14,008 KB |
testcase_63 | AC | 1 ms
4,376 KB |
testcase_64 | AC | 1 ms
4,352 KB |
ソースコード
/*under Implementation K回の試行で閉じたサイクルにたどり着かない場合があり、これをO(N)で計算する実装ができてない */ #include<bits/stdc++.h> #include<unistd.h> #define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i) #define rep(i,a,b) for(int i=int(a);i<int(b);++i) #define All(x) (x).begin(),(x).end() #define DEBUG(x) cerr<<(x)<<endl using namespace std; typedef long long ll; typedef pair<ll,ll> P; class node_type { public: int v; bool s; node_type(const int v, const bool s) : v(v), s(s) {} }; ll N,K; vector<ll> p; vector<P> incycle;//(何番目の閉じたサイクル内にいるか,サイクルの何処に位置するか) vector<P> tocycle;//(閉じたサイクルのどの数字に最初に当たるか、そこまでの長さ) vector<int> tocnt;//閉じたサイクルに行くまでの手数 vector<vector<P>> cycle;//(サイクルのk番目のP上での位置、スタート地点から何個P同士の境界を越えたか) vector<bool> outcycle; vector<P> ans; vector<vector<ll>> tree; std::vector<int> LA; std::vector<int> path; std::vector<node_type> stuck; void rsz(){ p.resize(N); incycle.resize(N); tocycle.resize(N); tocnt.resize(N); outcycle.resize(N,false); ans.resize(N); tree.resize(N); LA.resize(N,-1); stuck.reserve(N); } void cycle_detection(){ vector<bool> used(N,false); vector<int> prev(N,-1); int k=1; REP(i,N){ if(used[i]||incycle[i].first!=-1||prev[i]!=-1) continue; int j=i,pre=-1; bool out=false; while(!used[j]){ used[j]=true; prev[j]=pre; pre=j; j+=p[j]; j%=N; if(incycle[j].first!=-1||outcycle[j]){ out=true; break; } } if(out) {//サイクルに合流する数字は別に計算する for(int v=pre;v!=-1;v=prev[v]){ outcycle[v]=true; } continue; } cycle.resize(k+1); int u = pre, t = 0, num = 0; while(u!=j){ u=prev[u]; } for(int v=prev[u];v!=-1;v=prev[v]){ outcycle[v]=true; } do{ cycle[k].push_back(P(u,t)); incycle[u] = P(k,num); u+=p[u]; if(u>=N){ u-=N; t++; } num++; }while(u!=j); k++; } } P outcycle_calculate(int i){ if(incycle[i].first!=-1){ return P(i,0); } if(tocycle[i].first!=-1){ return tocycle[i]; } P res=outcycle_calculate((i+p[i])%N); tocnt[i]=tocnt[(i+p[i])%N]+1; tree[(i+p[i])%N].push_back(i); return tocycle[i]=P(res.first,res.second+p[i]); } P Ans_calculate(int start){ ll res=start; ll remain=K; if(incycle[res].first==-1){ remain-=tocnt[res]; res+=tocycle[res].second; } if(remain>0){ int C = incycle[res%N].first, num=incycle[res%N].second; ll LtoF = (cycle[C].back().first>=cycle[C][0].first); ll clen = N*(cycle[C].back().second + LtoF ); ll csz = cycle[C].size(); res += clen*(remain/csz); remain%=csz; int last=(num+remain)%csz; if(last<num){ ll border = cycle[C].back().second - cycle[C][num].second -1 + LtoF + cycle[C][last].second; if(border!=-1){ res += N - cycle[C][num].first + N*border + cycle[C][last].first; } else{ res += cycle[C][last].first - cycle[C][num].first; } } else{ ll border = cycle[C][last].second - cycle[C][num].second -1; if(border!=-1){ res += N - cycle[C][num].first + N*border + cycle[C][last].first; } else{ res += cycle[C][last].first - cycle[C][num].first; } } remain=0; } return P(res+1,remain); } void makeLA(int root){ stuck.emplace_back(root, true); while (!stuck.empty()) { if (stuck.back().s) { stuck.back().s = false; const int v = stuck.back().v; path.push_back(v); if(path.size()>K) LA[v] = path[(int)path.size()-K-1]; for (const int e : tree[v]) { stuck.emplace_back(e, true); } } else { stuck.pop_back(); path.pop_back(); } } return ; } int main(){ cin>>N>>K; rsz(); REP(i,N){ cin>>p[i]; incycle[i] = P(-1,-1); tocycle[i] = P(-1,-1); if(p[i]==N){ incycle[i] = P(0,0); cycle.push_back({P(i,0)}); } } cycle_detection(); //REP(i,cycle.size()) REP(j,cycle[i].size()) cerr<<cycle[i][j].first<<" \n"[j==cycle[i].size()-1]; REP(i,N){ outcycle_calculate(i); //cout<<i<<endl<<tocycle[i].first<<" "<<tocycle[i].second<<endl; } REP(i,N) ans[i]=Ans_calculate(i); REP(i,N){ if(ans[i].second!=0){ if(LA[i]==-1) makeLA(tocycle[i].first); cout<<i+1+tocycle[i].second - tocycle[LA[i]].second<<endl; }else{ cout<<ans[i].first<<endl; } } }