結果

問題 No.515 典型LCP
ユーザー LayCurse
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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);
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0