oj.uz

Submission #533823

# Submission time Handle Problem Language Result Execution time Memory
533823 2022-03-07T11:21:43 Z amunduzbaev Brperm (RMI20_brperm) C++17
0 / 100
 1259 ms 90380 KB 
#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(i + 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]);
		}
	}
	
	//~ for(int j=0;j<=3;j++){
		//~ for(int i=0;i + (1 << j)<=n;i++){
			//~ cout<<is[j][i]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
}

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

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 4956 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 4956 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1259 ms 90380 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 4956 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -