oj.uz

Submission #485219

# Submission time Handle Problem Language Result Execution time Memory
485219 2021-11-06T15:20:01 Z ETK Brperm (RMI20_brperm) C++14
0 / 100
 458 ms 121132 KB 
#include <bits/stdc++.h>
#include "brperm.h"
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=5e5+5,P=1e9+7,B=37;
int f[N][20],g[N][20],base[20],b[N][20],t[N],n;
int mul(int a,int b){return 1ll*a*b%P;}
int add(int a,int b){return a+b>=P?a+b-P:a+b;}
int sub(int a,int b){return a-b<0?a-b+P:a-b;}
void init(int m,const char s[]){
    n=m;
    base[19]=B;
    per(i,18,0)base[i]=mul(base[i+1],base[i+1]);
    rep(i,0,19){
        b[0][i]=1;
        rep(j,1,n-1)b[j][i]=mul(b[j-1][i],base[i]);
    }
    rep(i,0,19){//straighthash
        t[0]=s[0]-'a'+1;
        rep(j,1,n-1)t[j]=add(s[j]-'a'+1,mul(t[j-1],base[i]));
        f[0][i]=t[(1<<i)-1];
        rep(j,1,n-(1<<i)){
            f[j][i]=sub(t[j+(1<<i)-1],mul(t[j-1],b[1<<i][i]));
        }
    }
    rep(i,0,n-1)g[i][0]=s[i]-'a'+1;
    //brpermhash
    rep(j,1,19)rep(i,1,n-(1<<j)){
        g[i][j]=add(mul(g[i][j-1],base[j]),g[i+(1<<j)][j-1]);
    }
}
int query(int i,int k){return i+(1<<k)<=n&&f[i][k]==g[i][k];}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 458 ms 121132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -