Submission #1218128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218128		KindaGoodGames	Brperm (RMI20_brperm)	C++20	50 / 100	2459 ms	2416 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 = 250;
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;
}

Compilation message (stderr)

brperm.cpp:1:47: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("O3, unroll-loops, Ofast")
      |                                               ^
brperm.cpp:1:47: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
In file included from brperm.cpp:3:
brperm.h:4:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
    4 | void init(int n, const char s[]);
      |                                ^
brperm.h:4:32: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
brperm.h:4:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
brperm.h:4:32: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
brperm.h:5:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
    5 | int query(int i, int k);
      |                       ^
brperm.h:5:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
brperm.h:5:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
brperm.h:5:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
brperm.cpp:12:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   12 | int rev(int a, int p){
      |                     ^
brperm.cpp:12:21: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
brperm.cpp:25:38: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   25 | void init(int32_t N, const char arr[]) {
      |                                      ^
brperm.cpp:25:38: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
brperm.cpp:34:35: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   34 | int32_t query(int32_t l, int32_t k) {
      |                                   ^
brperm.cpp:34:35: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]

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