結果
問題 | No.1013 〇マス進む |
ユーザー | otamay6 |
提出日時 | 2019-11-08 16:43:51 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,411 bytes |
コンパイル時間 | 2,253 ms |
コンパイル使用メモリ | 185,332 KB |
実行使用メモリ | 8,964 KB |
最終ジャッジ日時 | 2023-10-13 07:10:26 |
合計ジャッジ時間 | 10,337 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,368 KB |
testcase_01 | AC | 1 ms
4,368 KB |
testcase_02 | AC | 1 ms
4,372 KB |
testcase_03 | AC | 2 ms
4,368 KB |
testcase_04 | AC | 2 ms
4,372 KB |
testcase_05 | AC | 2 ms
4,372 KB |
testcase_06 | WA | - |
testcase_07 | AC | 3 ms
4,372 KB |
testcase_08 | AC | 3 ms
4,368 KB |
testcase_09 | AC | 3 ms
4,368 KB |
testcase_10 | WA | - |
testcase_11 | AC | 2 ms
4,368 KB |
testcase_12 | WA | - |
testcase_13 | AC | 7 ms
4,368 KB |
testcase_14 | AC | 82 ms
5,760 KB |
testcase_15 | AC | 134 ms
7,536 KB |
testcase_16 | AC | 124 ms
7,432 KB |
testcase_17 | AC | 75 ms
5,592 KB |
testcase_18 | AC | 89 ms
6,180 KB |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | AC | 67 ms
5,504 KB |
testcase_22 | AC | 93 ms
6,264 KB |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | AC | 30 ms
4,372 KB |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | AC | 57 ms
5,228 KB |
testcase_31 | AC | 108 ms
6,652 KB |
testcase_32 | AC | 80 ms
5,624 KB |
testcase_33 | AC | 80 ms
5,760 KB |
testcase_34 | AC | 130 ms
7,400 KB |
testcase_35 | AC | 121 ms
7,364 KB |
testcase_36 | AC | 9 ms
4,372 KB |
testcase_37 | AC | 9 ms
4,372 KB |
testcase_38 | AC | 142 ms
7,716 KB |
testcase_39 | AC | 45 ms
4,644 KB |
testcase_40 | AC | 128 ms
7,336 KB |
testcase_41 | AC | 32 ms
4,372 KB |
testcase_42 | AC | 77 ms
5,532 KB |
testcase_43 | AC | 50 ms
4,956 KB |
testcase_44 | AC | 81 ms
5,700 KB |
testcase_45 | AC | 70 ms
5,596 KB |
testcase_46 | AC | 34 ms
4,372 KB |
testcase_47 | AC | 76 ms
5,532 KB |
testcase_48 | AC | 92 ms
6,272 KB |
testcase_49 | AC | 130 ms
7,320 KB |
testcase_50 | AC | 110 ms
6,620 KB |
testcase_51 | AC | 95 ms
6,488 KB |
testcase_52 | AC | 20 ms
4,372 KB |
testcase_53 | AC | 28 ms
4,416 KB |
testcase_54 | AC | 121 ms
7,328 KB |
testcase_55 | AC | 36 ms
4,384 KB |
testcase_56 | AC | 152 ms
8,328 KB |
testcase_57 | AC | 104 ms
6,668 KB |
testcase_58 | AC | 177 ms
8,896 KB |
testcase_59 | AC | 176 ms
8,964 KB |
testcase_60 | AC | 174 ms
8,824 KB |
testcase_61 | WA | - |
testcase_62 | WA | - |
testcase_63 | AC | 1 ms
4,372 KB |
testcase_64 | AC | 2 ms
4,372 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; const int MAX_N=100010; 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; void rsz(){ p.resize(N); incycle.resize(N); tocycle.resize(N); tocnt.resize(N); outcycle.resize(N,false); } 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; 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); } 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; } vector<P> ans(N); REP(i,N) ans[i]=Ans_calculate(i); REP(i,N) cout<<ans[i].first<<endl; }