結果

問題 No.2162 Copy and Paste 2
ユーザー lam6er
提出日時 2025-03-26 16:03:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 302 ms / 7,000 ms
コード長 1,580 bytes
コンパイル時間 1,892 ms
コンパイル使用メモリ 194,216 KB
実行使用メモリ 36,992 KB
最終ジャッジ日時 2025-03-26 16:03:34
合計ジャッジ時間 7,102 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void file()’:
main.cpp:24:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   24 |         freopen("proud.in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:25:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   25 |         freopen("proud.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:67:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |         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=1;
        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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0