Submission #1076421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076421		surgutti	Brperm (RMI20_brperm)	C++17	0 / 100	37 ms	52560 KiB

brperm

#include "brperm.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const LL mod = 1e9 + 9;
const LL base = 2137;

const int N = 100000 + 7;
const int L = 20;

LL p[1 << L];
LL h1[N][L];
LL h2[N][L][L];

void init(int n, const char s[]) {
	p[0] = 1;
	for (int i = 1; i < (1 << L); i++)
		p[i] = (p[i - 1] * base) % mod;

	for (int i = 0; i < n; i++)
		h1[i][0] = s[i] - 'a' + 1;

	for (int h = 0; h + 1 < L; h++)
		for (int i = 0; i + (1 << (h + 1)) <= n; i++)
			h1[i][h + 1] = (h1[i][h] + p[1 << h] * h1[i + (1 << h)][h]) % mod;
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < L; j++)
			h2[i][0][j] = s[i] - 'a' + 1;
	
	for (int j = L - 2; j >= 0; j--)
		for (int h = 0; h + 1 < L; h++)
			for (int i = 0; i + (1 << (h + 1)) <= n; i++)
				h2[i][h + 1][j] = (h2[i][h][j + 1] + p[1 << j] * h2[i + (1 << h)][h][j + 1]) % mod;
}

int query(int i, int k) {
	return h1[i][k] == h2[i][k][0];
}

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