oj.uz

Submission #827270

# Submission time Handle Problem Language Result Execution time Memory
827270 2023-08-16T10:27:18 Z rainboy Brperm (RMI20_brperm) C
0 / 100
 481 ms 23900 KB 
#include "brperm.h"

#define N	500000
#define L	18	/* L = floor(log2(N)) */
#define MD	0x7fffffff

int X = 11223344, Y = 55667788;

char nice[L + 1][N]; int n;

void init(int n_, const char *cc) {
	static int ppx[L + 1], ppy[L + 1], xx[N], yy[N], xx1[N], yy1[N], xx2[N], yy2[N];
	int i, l, l_;

	ppx[0] = X, ppy[0] = Y;
	for (l = 0; l <= L; l++) {
		ppx[l] = (long long) ppx[l - 1] * ppx[l - 1] % MD;
		ppy[l] = (long long) ppy[l - 1] * ppy[l - 1] % MD;
	}
	n = n_;
	for (l = 0; l <= L; l++) {
		if (l == 0)
			for (i = 0; i < n; i++)
				xx1[i] = yy1[i] = cc[i] - 'a';
		else {
			for (i = 0; i + (1 << l) <= n; i++) {
				xx[i] = ((long long) xx1[i] * ppx[l - 1] + xx1[i + (1 << l - 1)]) % MD;
				yy[i] = ((long long) yy1[i] * ppy[l - 1] + yy1[i + (1 << l - 1)]) % MD;
			}
			for (i = 0; i + (1 << l) <= n; i++)
				xx1[i] = xx[i], yy1[i] = yy[i];
		}
		for (l_ = 0; l_ <= l; l_++)
			if (l_ == 0)
				for (i = 0; i < n; i++)
					xx2[i] = yy2[i] = cc[i] - 'a';
			else {
				for (i = 0; i + (1 << l) - (1 << l - l_) < n; i++) {
					xx[i] = ((long long) xx2[i] * ppx[l_ - 1] + xx2[i + (1 << l - l_)]) % MD;
					yy[i] = ((long long) yy2[i] * ppy[l_ - 1] + yy2[i + (1 << l - l_)]) % MD;
				}
				for (i = 0; i + (1 << l) - (1 << l - l_) < n; i++)
					xx2[i] = xx[i], yy2[i] = yy[i];
			}
		for (i = 0; i + (1 << l) <= n; i++)
			nice[l][i] = xx1[i] == xx2[i] && yy1[i] == yy2[i];
	}
}

int query(int i, int l) {
	return i + (1 << l) <= n && nice[l][i];
}

Compilation message

brperm.c: In function 'init':
brperm.c:27:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   27 |     xx[i] = ((long long) xx1[i] * ppx[l - 1] + xx1[i + (1 << l - 1)]) % MD;
      |                                                              ~~^~~
brperm.c:28:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   28 |     yy[i] = ((long long) yy1[i] * ppy[l - 1] + yy1[i + (1 << l - 1)]) % MD;
      |                                                              ~~^~~
brperm.c:38:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   38 |     for (i = 0; i + (1 << l) - (1 << l - l_) < n; i++) {
      |                                      ~~^~~~
brperm.c:39:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   39 |      xx[i] = ((long long) xx2[i] * ppx[l_ - 1] + xx2[i + (1 << l - l_)]) % MD;
      |                                                                ~~^~~~
brperm.c:40:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |      yy[i] = ((long long) yy2[i] * ppy[l_ - 1] + yy2[i + (1 << l - l_)]) % MD;
      |                                                                ~~^~~~
brperm.c:42:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   42 |     for (i = 0; i + (1 << l) - (1 << l - l_) < n; i++)
      |                                      ~~^~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 37.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 33.0

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