Submission #646148

#	Time	Username	Problem	Language	Result	Execution time	Memory
646148		Alex_tz307	Brperm (RMI20_brperm)	C++17	100 / 100	512 ms	158488 KiB

brperm

#include <bits/stdc++.h>
#include "brperm.h"
 
using namespace std;
 
const int kN = 5e5;
const int kLog = 19;
const int base[] = {29, 31};
const int mod[] = {(int)1e9 + 7, (int)1e9 + 9};
int N, 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 k, int t) {
  return add(hsh[t][i][k], mod[t] - mult(hsh[t][i + (1 << k)][k], p[t][kLog], mod[t]), mod[t]);
}
 
void init(int n, const char s[]) {
  N = n;
 
  for (int i = 0; i < 2; ++i) {
    p[i][0] = base[i];
  }
  for (int k = 1; k <= kLog; ++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 <= kLog; ++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][kLog - 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 <= kLog; ++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][kLog - k], brHash[j][i + (1 << (k - 1))][k - 1], mod[j]), mod[j]);
      }
    }
  }
 
}
 
int query(int i, int k) {
  i += 1;
  if (k >= 20 || i + (1 << k) - 1 > N) {
    return 0;
  }
  return getHsh(i, k, 0) == brHash[0][i][k] && getHsh(i, k, 1) == brHash[1][i][k];
}

• Subtask 1: 13 / 13
• Subtask 2: 37 / 37
• Subtask 3: 17 / 17
• Subtask 4: 33 / 33