Submission #1218117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218117		KindaGoodGames	Brperm (RMI20_brperm)	C++20	50 / 100	3095 ms	2056 KiB

brperm

// #pragma GCC optimize("O3, unroll-loops, Ofast")

#include "brperm.h"
#include<bits/stdc++.h>
#include<random>
#include<chrono>
#define int long long 
using namespace std;

const int MAXN = 500000;
const int ITERATIONS = 500;
int rev(int a, int p){
    int r = 0;
    int p2 = 1 << p;
    for(int i = 0; i < p; i++){
        int bit = (a & (1<<i)) > 0;
        r += (1<<(p-i-1)) * bit;
    } 
    return r;
}
char str[MAXN];
int n;
mt19937 rng;

void init(int32_t N, const char arr[]) {
  rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
  n = N; 
  for(int i = 0; i < n; i++){
    str[i] = arr[i];
  }
  return;
}

int32_t query(int32_t l, int32_t k) { 
    int p2 = 1 << k; 
    int r = l +p2-1;
    if(l + p2 > n) return 0;

    bool valid = true;
    // for(int i = l; i < l+p2; i++){
    //   int np = rev(i-l, k)+l; 
    //   if(str[np] != str[i]) return 0; 
    // }
    for(int t = 0; t < ITERATIONS; t++){
      int i = uniform_int_distribution<int>(0, p2-1)(rng) + l;
      
      int np = rev(i-l, k)+l; 
      if(str[np] != str[i]) {
        return 0; 
      }
    }
 
    return valid;
}

• Subtask 1: 13 / 13
• Subtask 2: 37 / 37
• Subtask 3: 0 / 17
• Subtask 4: 0 / 33