oj.uz

Submission #596575

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

#define all(x) (x.begin(),x.end())
#define ll long long

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

using namespace std;

int dp[LOG][LOG][MAXN];
ll pot[MAXN], sv[MAXN];
ll invPot[MAXN];
int calcOp[MAX];
vector<int> a,b;

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;
}

char S[MAX];
int N;

void init(int n, const char s[]) {
  for(int i = 0; i < n; i++){
    for(int j = 19, p = 1; j >= 0; j--, p <<= 1)
      if((i>>j)&1)
        calcOp[i] += p;
  }

  if(n > 100000 ){
    N = n;

    for(int i = 0; i < n; i++){
      S[i] = s[i];
      if(S[i] == 'a') a.push_back(i);
      else b.push_back(i);
    }
    return;
  }

  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) {
    if(N > 100000){

      if(k == 0) return 1;

      if((1<<k) <= 100) {
        for(int j = i, z = 0; j < (1<<k)+i; j++, z++){
          int x = calcOp[z];
          x >>= (20-k);
          if(S[j] != S[i+x])
            return 0;
        }
        return 1;
      }

      int cnt = 100;

      int l = lower_bound(a.begin(),a.end(),i)-a.begin();
      int r = lower_bound(a.begin(),a.end(),i+(1<<k))-a.begin();

      if(r-l)
      while(cnt--){
        int id = rand() % (r-l);
        int guy = a[id+l];
        id = guy-i;

        int x=calcOp[id];
        x >>= (20-k);

        if(S[id+i] != S[x+i])
          return 0;
      }

      cnt = 100;

      l = lower_bound(b.begin(),b.end(),i)-b.begin();
      r = lower_bound(b.begin(),b.end(),i+(1<<k))-b.begin();

      if(r-l)
      while(cnt--){
        int id = rand() % (r-l);
        int guy = b[id+l];
        id = guy-i;

        int x=calcOp[id];
        x >>= (20-k);

        if(S[id+i] != S[x+i])
          return 0;
      }      

      return 1;
    }
    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 1884 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 1884 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 149 ms 121076 KB Output is correct
4 Correct 154 ms 121092 KB Output is correct
5 Correct 153 ms 121016 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 637 ms 6272 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 1884 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 149 ms 121076 KB Output is correct
4 Correct 154 ms 121092 KB Output is correct
5 Correct 153 ms 121016 KB Output is correct
6 Incorrect 637 ms 6272 KB Output isn't correct
7 Halted 0 ms 0 KB -