Submission #858250

#	Time	Username	Problem	Language	Result	Execution time	Memory
858250		mircea_007	Brperm (RMI20_brperm)	C++17	100 / 100	1487 ms	15848 KiB

brperm

#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 / 13
• Subtask 2: 37 / 37
• Subtask 3: 17 / 17
• Subtask 4: 33 / 33