oj.uz

Submission #533825

# Submission time Handle Problem Language Result Execution time Memory
533825 2022-03-07T11:24:54 Z amunduzbaev Brperm (RMI20_brperm) C++17
100 / 100
 1348 ms 50348 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(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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2636 KB Output is correct
2 Correct 4 ms 2636 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2636 KB Output is correct
2 Correct 4 ms 2636 KB Output is correct
3 Correct 182 ms 11548 KB Output is correct
4 Correct 185 ms 11428 KB Output is correct
5 Correct 194 ms 11472 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1348 ms 49796 KB Output is correct
2 Correct 1341 ms 50348 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2636 KB Output is correct
2 Correct 4 ms 2636 KB Output is correct
3 Correct 182 ms 11548 KB Output is correct
4 Correct 185 ms 11428 KB Output is correct
5 Correct 194 ms 11472 KB Output is correct
6 Correct 1348 ms 49796 KB Output is correct
7 Correct 1341 ms 50348 KB Output is correct
8 Correct 1345 ms 50248 KB Output is correct
9 Correct 1334 ms 50328 KB Output is correct
10 Correct 1339 ms 50304 KB Output is correct