結果
| 問題 | No.1013 〇マス進む |
| ユーザー |
 otamay6
|
| 提出日時 | 2019-11-08 15:42:09 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 4,195 bytes |
| コンパイル時間 | 3,336 ms |
| コンパイル使用メモリ | 177,776 KB |
| 実行使用メモリ | 814,348 KB |
| 最終ジャッジ日時 | 2023-10-13 07:09:06 |
| 合計ジャッジ時間 | 6,032 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,348 KB |
| testcase_01 | AC | 2 ms
5,404 KB |
| testcase_02 | MLE | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
ソースコード
/*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;
ll p[MAX_N];
P incycle[MAX_N];//(何番目の閉じたサイクル内にいるか,サイクルの何処に位置するか)
P tocycle[MAX_N];//(閉じたサイクルのどの数字に最初に当たるか、そこまでの長さ)
int tocnt[MAX_N];//閉じたサイクルに行くまでの手数
vector<vector<P>> cycle;//(サイクルのk番目のP上での位置、スタート地点から何個P同士の境界を越えたか)
ll toK[MAX_N],toK1[MAX_N];//数字からK回行く長さとK-1回行く長さ
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) continue;
int j=i;
bool out=false;
while(1){
if(incycle[j].first!=-1){
out=true;
break;
}
if(used[j]) break;
if(prev[(j+p[i])%N]!=-1){
out=true;
break;
}
used[j]=true;
prev[(j+p[j])%N]=j;
j+=p[j];
j%=N;
}
if(out) continue;//サイクルに合流する数字は別に計算する
cycle.resize(k+1);
int u = prev[j], t = 0, num = 0;
while(u!=j){
u=prev[u];
}
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;
REP(i,N){
cin>>p[i];
incycle[i].first = -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;
}