Submission #827275

#	Time	Username	Problem	Language	Result	Execution time	Memory
827275		rainboy	Brperm (RMI20_brperm)	C11	100 / 100	530 ms	27260 KiB

brperm

#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 = 1; 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 (stderr)

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: 13 / 13
• Subtask 2: 37 / 37
• Subtask 3: 17 / 17
• Subtask 4: 33 / 33