oj.uz

Submission #858246

# Submission time Handle Problem Language Result Execution time Memory
858246 2023-10-07T18:05:26 Z mircea_007 Brperm (RMI20_brperm) C++17
0 / 100
 1457 ms 14244 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];
} 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[] ){
  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 ){
  return data.ans[k][i];
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 37.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 33.0

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