oj.uz

Submission #596571

# Submission time Handle Problem Language Result Execution time Memory
596571 2022-07-14T20:37:31 Z CaroLinda Brperm (RMI20_brperm) C++14
50 / 100
 672 ms 153012 KB 
#include "brperm.h"
#include <bits/stdc++.h>

#define ll long long

const ll PRIME = 37LL;
const ll MOD = 1e9+7;
const int LOG = 20;
const int MAXN = 1e5+10;

using namespace std;

int dp[LOG][LOG][MAXN];
ll pot[MAXN], sv[MAXN];
ll invPot[MAXN];

ll expo(ll b, ll e){
  if(e == 0)
    return 1LL;

  ll aux = expo(b, e>>1LL);
  aux = (aux*aux) % MOD;

  if(e&1){
    aux = (aux*b) % MOD;
  }

  return aux;
}

void init(int n, const char s[]) {
  pot[0] = 1LL;

  for(int i = 1; i <= n; i++)
    pot[i] = (pot[i-1] * PRIME) % MOD;

  for(int i = 0; i < n; i++){
    sv[i] = (i == 0) ? 0 : sv[i-1];
    sv[i] += (pot[i] * (s[i]-'a'+1))%MOD;
    sv[i] %= MOD;
  }

  invPot[0] = 1;
  invPot[1] = expo(PRIME, MOD-2);
  for(int i = 2; i <= n; i++)
    invPot[i] = (invPot[i-1] * invPot[1] ) % MOD;

  for(int i = 0; i < LOG; i++)
    for(int j = 0; j < n ; j++){
      dp[0][i][j] = s[j]-'a'+1;
    }

  for(int i = 1; i < LOG; i++)
    for(int j = 0; j < LOG-1; j++)
      for(int g = 0; g+(1<<i)-1 < n; g++){
        dp[i][j][g] = dp[i-1][j+1][g];
        ll toSum = dp[i-1][j+1][g+(1<<(i-1))]*pot[(1<<j)];

        toSum %= MOD;
        dp[i][j][g] += toSum;

        if(dp[i][j][g] >= MOD)
          dp[i][j][g] -= MOD;
      }

}

int query(int i, int k) {
    int l = i, r = (1<<k)+l-1;
    ll hashSeq = sv[r]-( l == 0 ? 0 : sv[l-1]);
    hashSeq += MOD;
    hashSeq %= MOD;
    hashSeq *= invPot[l];
    hashSeq %= MOD;

    return hashSeq == dp[k][0][i];
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 155 ms 121620 KB Output is correct
4 Correct 165 ms 121612 KB Output is correct
5 Correct 152 ms 121548 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 155 ms 121620 KB Output is correct
4 Correct 165 ms 121612 KB Output is correct
5 Correct 152 ms 121548 KB Output is correct
6 Incorrect 672 ms 153012 KB Output isn't correct
7 Halted 0 ms 0 KB -