oj.uz

Submission #858250

# Submission time Handle Problem Language Result Execution time Memory
858250 2023-10-07T18:19:22 Z mircea_007 Brperm (RMI20_brperm) C++17
100 / 100
 1487 ms 15848 KB 
#include "brperm.h"

#include <random>
#include <time.h>

using ll = long long;

const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;

int BASE; // runtime constant, random value

/*

  Nlog^2N timp si memorie:

  // step, n, puteri ale lui 2
  // pare -> prima jumatate
  // impare -> a doua jumate

  hash( i, step, n, BASE ) = hash( i, step * 2, n / 2, BASE ) * BASE^(n/2) + hash( i + step, step * 2, n / 2, BASE )

  // obs: parametrul BASE ramane constant

  H( i, step, n ) = BASE^(n/2) * H( i, step * 2, n / 2 ) + H( i + step, step * 2, n / 2 )

  // step * n = 2^k constant

  pentru fiecare k:
    init: H[i] = v[i]
    for step=2^k-1..1:
      //H[i] = BASE^((2^k/step)/2) * H[i] + H[i + step]
      H[i] = BASE^(2^k-1/step) * H[i] + H[i + step]
  
*/

const int MAXN = 500 * 1000;
const int MAXL = 19;

struct Persist {
  char ans[MAXL][MAXN];
  int n;
} data;

void rev_hash( int n, int k, const char s[], int h[], const int BASE, const int MOD ){
  for( int i = 0 ; i < n ; i++ )
    h[i] = s[i] - 'a';

  if( !k )
    return;

  ll b = BASE;
  for( int step = 1 << (k - 1) ; step ; step >>= 1 ){    
    for( int i = 0 ; i + step < n ; i++ )
      h[i] = (b * h[i] + h[i + step]) % MOD;

    b = (b * b) % MOD;
  }
}

void init( int n, const char s[] ){
  data.n = n;
  
  std::mt19937 rng( clock() );
  BASE = rng() % 1000; // keep it reasonable

  int *rev_hash_1 = new int[n];
  int *rev_hash_2 = new int[n];

  for( int k = 0 ; (1 << k) <= n ; k++ ){
    rev_hash( n, k, s, rev_hash_1, BASE, MOD1 );
    rev_hash( n, k, s, rev_hash_2, BASE, MOD2 );

    int len = (1 << k);
    ll hash1 = 0, hash2 = 0;
    ll pBASE1 = MOD1 - 1, pBASE2 = MOD2 - 1;

    for( int i = 0 ; i + 1 < len ; i++ ){
      hash1 = (hash1 * BASE + (s[i] - 'a')) % MOD1;
      hash2 = (hash2 * BASE + (s[i] - 'a')) % MOD2;

      pBASE1 = (pBASE1 * BASE) % MOD1;
      pBASE2 = (pBASE2 * BASE) % MOD2;
    }

    // pBASE = -BASE^(len-1)

    for( int i = len - 1 ; i < n ; i++ ){
      hash1 = (hash1 * BASE + (s[i] - 'a')) % MOD1;
      hash2 = (hash2 * BASE + (s[i] - 'a')) % MOD2;

      data.ans[k][i - len + 1] = (rev_hash_1[i - len + 1] == hash1 && rev_hash_2[i - len + 1] == hash2);

      hash1 = (hash1 + pBASE1 * (s[i - len + 1] - 'a')) % MOD1;
      hash2 = (hash2 + pBASE2 * (s[i - len + 1] - 'a')) % MOD2;
    }
  }

  delete []rev_hash_1;
  delete []rev_hash_2;
}

int query( int i, int k ){
  if( i < 0 || i + (1 << k) > data.n ) // se pare ca testele nu respecta enuntul
    return 0;
  
  return data.ans[k][i];
}

Subtask #1
13.0 / 13.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6632 KB Output is correct
3 Correct 235 ms 9888 KB Output is correct
4 Correct 233 ms 9884 KB Output is correct
5 Correct 238 ms 10064 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1446 ms 13760 KB Output is correct
2 Correct 1444 ms 15540 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6632 KB Output is correct
3 Correct 235 ms 9888 KB Output is correct
4 Correct 233 ms 9884 KB Output is correct
5 Correct 238 ms 10064 KB Output is correct
6 Correct 1446 ms 13760 KB Output is correct
7 Correct 1444 ms 15540 KB Output is correct
8 Correct 1487 ms 15564 KB Output is correct
9 Correct 1462 ms 15848 KB Output is correct
10 Correct 1474 ms 15576 KB Output is correct