oj.uz

Submission #746335

# Submission time Handle Problem Language Result Execution time Memory
746335 2023-05-22T11:25:59 Z doowey Brperm (RMI20_brperm) C++14
0 / 100
 25 ms 5460 KB 
#include <bits/stdc++.h>
#include "brperm.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int MOD = (int)1e9 + 9;
const int N = (int)5e5 + 10;
const int K = 19;
const int B = 77;
vector<char> S;
int dp[N][K][K];
int pwr[N];

int make(int i, int step, int lim){
    if(dp[i][step][lim] != 0) return dp[i][step][lim];
    if(step == lim){
        //cout << i << " ";
        return S[i] - 'a' + 1;
    }
    int lef, rig;
    lef = make(i, step + 1, lim);
    rig = make(i + (1 << step), step + 1, lim);
    //cout << "merge: " << lef << " + " << rig << "\n";
    lef += (rig * 1ll * pwr[(1<<(lim-step - 1))]) % MOD;
    if(lef >= MOD) lef -= MOD;
    return dp[i][step][lim]=lef;
}

int H[N][K];

int make2(int i, int step){
    if(H[i][step] != 0) return H[i][step];
    if(step == 0){
        return S[i] - 'a' + 1;
    }
    int lef = make2(i, step - 1);
    int rig = make2(i + (1 << (step - 1)), step - 1);
    lef += (rig * 1ll * pwr[(1 << (step - 1))]) % MOD;
    if(lef >= MOD) lef -= MOD;
    return H[i][step] = lef;
}

void init(int n, const char s[]) {
    pwr[0] = 1;
    for(int i = 1; i <= n; i ++ ) pwr[i] = (pwr[i - 1] * 1ll * B) % MOD;
    for(int i = 0 ; i < n; i ++ ){
        S.push_back(s[i]);
    }
}

int query(int i, int k) {
    //int ca = make(i, 0, k);
    //int cb = make2(i, k);
    int sz = (1 << k);
    vector<char> A(sz), B(sz);
    for(int j = 0 ; j < sz; j ++ ){
        A[j] = S[i + j];
        int f = 0;
        for(int p = 0; p < k ; p ++ ){
            if((j & (1 << p))){
                f |= (1 << (k - p - 1));
            }
        }
        B[f] = S[i + j];
    }

    //cout << ca << " " << cb << " |\n";
    return (A == B);
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 948 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 948 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 5460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 948 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -