oj.uz

Submission #1076421

# Submission time Handle Problem Language Result Execution time Memory
1076421 2024-08-26T13:44:32 Z surgutti Brperm (RMI20_brperm) C++17
0 / 100
 37 ms 52560 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 13912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 13912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 13912 KB Output isn't correct
2 Halted 0 ms 0 KB -