結果

問題 No.2162 Copy and Paste 2
ユーザー qwer1234qwer
提出日時 2025-03-17 16:43:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,475 bytes
コンパイル時間 2,130 ms
コンパイル使用メモリ 192,768 KB
実行使用メモリ 125,392 KB
最終ジャッジ日時 2025-03-17 16:43:22
合計ジャッジ時間 4,474 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 5 WA * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void file()’:
main.cpp:25:8: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   25 | freopen("proud.in","r",stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:26:8: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   26 | freopen("proud.out","w",stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:64:6: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   64 | scanf("%s",s);
      | ~~~~~^~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=(j);i<=(k);++i)
#define NFOR(i,j,k) for(int i=(j);i>=(k);--i)
#define mkp make_pair
#define fst first
#define sec second
#define inl inline
#define pb push_back
#define el_phy_kongroo return 0
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned int ui;
typedef pair< int,int > pii;
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+ch-'0',ch=getchar();}
return s*w;
}
void file()
{
freopen("proud.in","r",stdin);
freopen("proud.out","w",stdout);
}
void teltim(int x)
{
clock_t c1=0;
if(x) c1=clock();
else cerr<<endl<<clock()-c1<<"ms"<<endl;
}
const int N=2e6+5;
char s[N];
int n;
int z[N];
void sov()
{
z[0]=n;
int i=1,j=0;
while(i<n)
{
while(i+j<n&&s[j]==s[i+j]) j++;
z[i]=j;
if(j==0) 
{
i++;
continue;
}
int k=2;
while(i+k<n&&k+z[k]<j)
{
z[i+k]=z[k];
k++;
}
i+=k;j-=k;
}
}
int mx[20][N],nxt[20][N],mn[N];
int main()
{
//file();
scanf("%s",s);
n=strlen(s);
sov();
FOR(i,0,n-1) mx[0][i]=z[i];
FOR(i,0,n-1)
{
if(i==n-1) nxt[0][i]=i;
else nxt[0][i]=i+1;
}
FOR(i,1,19) FOR(j,0,n-1)
{
int k=nxt[i-1][j];
nxt[i][j]=nxt[i-1][k];
mx[i][j]=max(mx[i-1][j],mx[i-1][k]);
}
FOR(i,1,n-1)
{
mn[i]=min(mn[i],mn[i-1]);
int x=mn[i]+1,j=i+1,z=i+1;
while(j<n)
{
if(mx[19][j]<z) break;
NFOR(k,19,0) if(mx[k][j]<z) j=nxt[k][j];
j+=z-1;
x-=z-1;
mn[j]=min(mn[j],x);
j++;
}
}
printf("%d",n+mn[n-1]);
el_phy_kongroo;
}
0