Submission #533825

#	Time	Username	Problem	Language	Result	Execution time	Memory
533825		amunduzbaev	Brperm (RMI20_brperm)	C++17	100 / 100	1348 ms	50348 KiB

brperm

#include "bits/stdc++.h"
using namespace std;
#include "brperm.h"
#ifndef EVAL
#include "grader.cpp"
#endif

const int N = 5e5 + 5;
const int P = 167;
const int mod = 1e9 + 7;
int pw[N], is[20][N];

struct BOR{
	int H[N << 1], is[N << 1];
	int MX;
	BOR(){
		MX = 0;
	}
	void add(int v, int c){
		int x = 1;
		for(int j=0;j<MX;j++){
			if(v >> j & 1) x = (x << 1 | 1);
			else x = (x << 1);
		}
		
		H[x] = c;
	}
	
	void calc(int u = 1, int i = 0){
		if(i == MX) return;
		calc(u << 1, i + 1);
		calc(u << 1 | 1, i + 1);
		H[u] = (H[u << 1] * 1ll * pw[(1 << (MX - i - 1))] + H[u << 1 | 1]) % mod;
	}
	
	void rec(int c, int u = 1, int i = 0){
		if(i == MX){
			H[u] = c;
			return;
		}
		
		is[u] ^= 1;
		rec(c, u << 1 | is[u], i + 1);
		H[u] = (H[u << 1 | is[u]] * 1ll * pw[(1 << (MX - i - 1))] + H[u << 1 | !is[u]]) % mod;
	}
}bor[19];

void init(int n, const char T[]) {
	vector<int> s(n);
	for(int i=0;i<n;i++) s[i] = T[i] - 'a';
	pw[0] = 1;
	for(int i=1;i<N;i++) pw[i] = pw[i-1] * 1ll * P % mod;
	for(int i=0;i<19;i++) bor[i].MX = i;
	int inv = 5988024; //~ pow(P, mod - 2)
	int H[19] {};
	
	for(int i=n-1;~i;i--){
		for(int j=0;j<19;j++){
			if(i + (1 << j) > n) continue;
			if(i + (1 << j) == n){
				for(int l=0;l<(1 << j);l++){
					bor[j].add(l, s[i + l]);
					H[j] = (H[j] * 1ll * P + s[i + l]) % mod;
				}
				bor[j].calc();
				is[j][i] = (bor[j].H[1] == H[j]);
				continue;
			}
			bor[j].rec(s[i]);
			H[j] = (H[j] - s[i + (1 << j)]) * 1ll * inv % mod;
			H[j] = (H[j] + s[i] * 1ll * pw[(1 << j) - 1]) % mod;
			is[j][i] = (bor[j].H[1] == H[j]);
		}
	}
}

int query(int i, int k) {
	if(!k) return 1;
	return is[k][i];
}

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