oj.uz

Submission #973900

# Submission time Handle Problem Language Result Execution time Memory
973900 2024-05-02T12:34:57 Z sleepntsheep Savez (COCI15_savez) C
120 / 120
 363 ms 26960 KB 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

unsigned rand_wide() { return 1llu * rand()*rand(); }
unsigned rand_wide2(unsigned l, unsigned r) { if (l==r)return l; return l+rand_wide()%(r-l); }

#define N 1000000
#define TN 2000000
#define N_ (TN+N+100)
#define M (N*N*2)

char s[N_];
int p, n, z, at[N+1], hash[N_], BASE, MOD = 1000000007;

int power(int a,int b)
{
    if (!b)return 1;
    int r= power(a,b/2);
    if(b&1)return r*1ll*r%MOD*a%MOD;
    return r*1ll*r%MOD;
}

int K[N_], B[N_], L[N_], R[N_], V[N_], alc;

int tnode(int x,int y)
{
    int p=++alc;
    K[p]=x;
    B[p]=rand_wide();
    L[p]=R[p]=0;
    V[p]=y;
    return p;
}
void split(int v,int*l,int*r,int k)
{
    if(!v){*l=*r=0;return;}
    if(K[v]<=k)
        split(R[v],R+v,r,k),*l=v;
    else
        split(L[v],l,L+v,k),*r=v;
}
void merge(int*v,int l,int r)
{
    if(!l||!r){*v=l^r;return;}
    if(B[l]>B[r])
        merge(R+l,R[l],r),*v=l;
    else
        merge(L+r,l,L[r]),*v=r;
}
void put(int*v,int key,int val)
{
    int t1,t2,t3;
    split(*v,&t2,&t3,key);
    split(t2,&t1,&t2,key-1);
    if(!t2) t2=tnode(key,val);
    else if(val>V[t2])V[t2]=val;
    merge(&t2,t1,t2);
    merge(v,t2,t3);
}
int get(int v,int key)
{
    while(v&&K[v]!=key)
    {
        if(K[v]<key)v=R[v];
        else v=L[v];
    }
    return V[v];
}


/*int *eh[TN+1], eo[TN+1];
void push(int i,int j)
{
    int o=eo[i]++;
    if(!o)eh[i]=(int*)realloc(eh[i],sizeof**eh*2);
    else eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
    eh[i][o]=j;
}*/

int main()
{
    srand(time(0));
    BASE = rand_wide2(200, MOD-1);

    scanf("%d", &n);
    for (int len, i = 0; i < n; ++i)
        scanf("%s", s+(at[i]=p)), at[i+1]=p+=strlen(s+at[i])+1;

    for (int i=0;i<n;++i)
        for(int bp=1,j=at[i];s[j];++j,bp=bp*1ll*BASE%MOD)
            hash[j] = bp * 1ll * s[j]%MOD;

    for (int i=1;i<=at[n];++i)
        if(s[i]>0) hash[i]=(hash[i]+hash[i-1])%MOD;

    int map=0;
    for(int i=n-1;i>=0;--i)
    {
        int dp=get(map,hash[at[i+1]-2])+1;

        for(int j=1;j<=at[i+1]-at[i]-1;++j)
        {
            if(hash[at[i]+j-1]*1ll*power(BASE,at[i+1]-1-at[i]-j)%MOD==(hash[at[i+1]-2]+MOD-hash[at[i+1]-2-j])%MOD)
                put(&map,hash[at[i]+j-1],dp);
        }
        if(dp>z)z=dp;
    }

    printf("%d",z);
}

Compilation message

savez.c: In function 'main':
savez.c:88:14: warning: unused variable 'len' [-Wunused-variable]
   88 |     for (int len, i = 0; i < n; ++i)
      |              ^~~
savez.c:87:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     scanf("%d", &n);
      |     ^~~~~~~~~~~~~~~
savez.c:89:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%s", s+(at[i]=p)), at[i+1]=p+=strlen(s+at[i])+1;
      |         ^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14680 KB Output is correct
2 Correct 4 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14704 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 13 ms 14684 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 18884 KB Output is correct
2 Correct 355 ms 18880 KB Output is correct
3 Correct 363 ms 18780 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14680 KB Output is correct
2 Correct 230 ms 18780 KB Output is correct
3 Correct 268 ms 18768 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 18872 KB Output is correct
2 Correct 150 ms 19872 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 18868 KB Output is correct
2 Correct 119 ms 19796 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 19360 KB Output is correct
2 Correct 99 ms 19792 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 21584 KB Output is correct
2 Correct 89 ms 21796 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 23896 KB Output is correct
2 Correct 68 ms 24136 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 24284 KB Output is correct
2 Correct 83 ms 24344 KB Output is correct
3 Correct 77 ms 26960 KB Output is correct