oj.uz

Submission #646145

# Submission time Handle Problem Language Result Execution time Memory
646145 2022-09-28T18:58:58 Z Alex_tz307 Brperm (RMI20_brperm) C++17
0 / 100
 420 ms 262144 KB 
#include <bits/stdc++.h>
#include "brperm.h"

using namespace std;

const int kN = 5e5;
const int kLog = 18;
const int base[] = {29, 31};
const int mod[] = {(int)1e9 + 7, (int)1e9 + 9};
int lg, p[2][1 + kLog];
int hsh[2][1 + kN + 1][1 + kLog];
int brHash[2][1 + kN][1 + kLog];

int add(int x, int y, int mod) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
  return x;
}

int mult(int x, int y, int mod) {
  return (int64_t)x * y % mod;
}

int getHsh(int i, int len, int k, int t) {
  return add(hsh[t][i][k], mod[t] - mult(hsh[t][i + len][k], p[t][lg], mod[t]), mod[t]);
}

void init(int n, const char s[]) {
  while ((1 << (lg + 1)) <= n) {
    lg += 1;
  }

  for (int i = 0; i < 2; ++i) {
    p[i][0] = base[i];
  }
  for (int k = 1; k <= lg; ++k) {
    for (int i = 0; i < 2; ++i) {
      p[i][k] = mult(p[i][k - 1], p[i][k - 1], mod[i]);
    }
  }

  for (int k = 0; k <= lg; ++k) {
    for (int i = n; i > 0; --i) {
      for (int j = 0; j < 2; ++j) {
        hsh[j][i][k] = add(mult(hsh[j][i + 1][k], p[j][k], mod[j]), s[i - 1] - 'a' + 1, mod[j]);
      }
    }
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 2; ++j) {
      brHash[j][i][0] = s[i - 1] - 'a' + 1;
    }
  }
  for (int k = 1; k <= lg; ++k) {
    for (int i = 1; i + (1 << k) - 1 <= n; ++i) {
      for (int j = 0; j < 2; ++j) {
        brHash[j][i][k] = add(brHash[j][i][k - 1], mult(p[j][lg - k], brHash[j][i + (1 << (k - 1))][k - 1], mod[j]), mod[j]);
      }
    }
  }
}

int query(int i, int k) {
  i += 1;
  return getHsh(i, 1 << k, lg - k, 0) == brHash[0][i][k] && getHsh(i, 1 << k, lg - k, 1) == brHash[1][i][k];
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 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 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 33.0

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