結果
問題 | No.515 典型LCP |
ユーザー |
![]() |
提出日時 | 2017-05-05 22:53:44 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,787 bytes |
コンパイル時間 | 1,455 ms |
コンパイル使用メモリ | 160,148 KB |
実行使用メモリ | 11,072 KB |
最終ジャッジ日時 | 2024-09-14 09:55:03 |
合計ジャッジ時間 | 3,338 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 13 RE * 2 |
ソースコード
#include<bits/stdc++.h>using namespace std;void rd(int &x){int k, m=0;x=0;for(;;){k = getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}void rd(long long &x){int k, m=0;x=0;for(;;){k = getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}int rd(char c[]){int i, sz=0;for(;;){i = getchar_unlocked();if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){break;}}c[sz++] = i;for(;;){i = getchar_unlocked();if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){break;}c[sz++] = i;}c[sz]='\0';return sz;}void wt_L(long long x){char f[20];int m=0, s=0;if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){putchar_unlocked('-');}while(s--){putchar_unlocked(f[s]+'0');}}template<class S, class T> inline S min_L(S a,T b){return a<=b?a:b;}template<class S, class T> inline S divup_L(S a, T b){return (a+b-1)/b;}char *S[100000], mem[1000100];int M, N, len[100000], result[3000000];long long d, x;unsigned long long *iS[100000], imem[1000100];int main(){int i, j, k, m, mx, s=0;long long fx, res=0;rd(N);for(i=0;i<N;i++){S[i] = mem+s;len[i] = rd(&mem[s]);s += len[i];}s = 0;for(i=0;i<N;i++){iS[i] = imem+s;m = divup_L(len[i],8);s += m;for(j=0;j<m;j++){iS[i][j] = 0;}for(j=0;j<len[i];j++){iS[i][j/8] += ((unsigned long long)S[i][j]) << (j%8)*8;}}rd(M);rd(x);rd(d);fx = x;for(k=0;k<M;k++){i = x / (N-1);j = x % (N-1);if(i > j){swap(i,j);}else{j++;}x += d;if(x >= N*(N-1)){x -= N * (N-1);}mx =min_L(len[i], len[j]);for(m=0;m+7<mx;m+=8){if(iS[i][m/8] != iS[j][m/8]){break;}}for( ;m <mx;m++ ){if(S[i][m] != S[j][m]){break;}}result[k] = m;res += m;if(fx==x){s = k+1;for(;;){k++;if(k >= M){break;}res += result[k%s];}break;}}wt_L(res);putchar_unlocked('\n');return 0;}// cLay varsion 20170505-3// --- original code ---// int N;// char *S[100000], mem[1000100];// int len[100000];// int M; ll x, d;//// ull *iS[100000], imem[1000100];// int result[3000000];//// {// int i, j, k, m, mx, s = 0;// ll fx;// ll res = 0;//// rd(N);// rep(i,N){// S[i] = mem+s;// rd(&mem[s]@len[i]);// s += len[i];// }//// s = 0;// rep(i,N){// iS[i] = imem+s;// m = len[i] /+ 8;// s += m;//// rep(j,m) iS[i][j] = 0;// rep(j,len[i]){// iS[i][j/8] += ((ull)S[i][j]) << (j%8)*8;// }//// }//// rd(M,x,d);// fx = x;// rep(k,M){// i = x / (N-1);// j = x % (N-1);// if(i > j) swap(i,j); else j++;//// x += d;// if(x >= N*(N-1)) x -= N * (N-1);//// mx = min(len[i],len[j]);// for(m=0;m+7<mx;m+=8) if(iS[i][m/8] != iS[j][m/8]) break;// for( ;m <mx;m++ ) if(S[i][m] != S[j][m]) break;// result[k] = m;// res += m;//// if(fx==x){// s = k+1;// for(;;){// k++;// if(k >= M) break;// res += result[k%s];// }// break;// }// }//// wt(res);// }