oj.uz

Submission #401719

# Submission time Handle Problem Language Result Execution time Memory
401719 2021-05-10T18:10:23 Z rama_pang Brperm (RMI20_brperm) C++17
0 / 100
 410 ms 72660 KB 
#include "brperm.h"

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX = 500005;
const int LOG = 18;

// Solution:
// B = Base
// StraightHash(B, L, K) = \sum_{i = L}^{L + 2^K - 1} B^{i - L} x_i
// BrPermHash(B, L, K) = BrPermHash(B^2, L, K - 1) + B * BrPermHash(B^2, L + 2^{K - 1}, K - 1)

int N;
string S;

int Base[LOG];
int BrPermHash[MAX][LOG];
int StraightHash[MAX][LOG];

void init(int n, const char s[]) {
  N = n, S = s;

  Base[LOG - 1] = 37;
  for (int i = LOG - 2; i >= 0; i--) {
    Base[i] = 1ll * Base[i + 1] * Base[i + 1] % MOD;
  }

  for (int L = N - 1; L >= 0; L--) {
    BrPermHash[L][0] = (S[L] - 'a' + 1);
    for (int K = 1; K < LOG; K++) {
      BrPermHash[L][K] = BrPermHash[L][K - 1];
      if (L + (1 << (K - 1)) <= N) {
        BrPermHash[L][K] += 1ll * Base[K] * BrPermHash[L + (1 << (K - 1))][K - 1] % MOD;
        BrPermHash[L][K] %= MOD;
      }
    }
  }

  for (int L = N - 1; L >= 0; L--) {
    for (int K = 0; K < LOG; K++) {
      StraightHash[L][K] = ((S[L] - 'a' + 1) + 1ll * Base[K] * StraightHash[L + 1][K]) % MOD;
    }
  }

  for (int K = 0; K < LOG; K++) {
    int power = 1;
    for (int i = 0; i < (1 << K); i++) {
      power = 1ll * power * Base[K] % MOD;
    }
    for (int L = 0; L < N; L++) {
      if (L + (1 << K) <= N) {
        StraightHash[L][K] += MOD - (1ll * power * StraightHash[L + (1 << K)][K] % MOD);
        StraightHash[L][K] %= MOD;
      }
    }
  }
}

int query(int i, int k) {
  return StraightHash[i][k] == BrPermHash[i][k];
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 37.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 33.0

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