oj.uz

답안 #827275

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
827275 2023-08-16T10:29:00 Z rainboy Brperm (RMI20_brperm) C
100 / 100
 530 ms 27260 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 = 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

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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 420 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 420 KB Output is correct
3 Correct 83 ms 4584 KB Output is correct
4 Correct 79 ms 5408 KB Output is correct
5 Correct 79 ms 5380 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 490 ms 22264 KB Output is correct
2 Correct 502 ms 27216 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 420 KB Output is correct
3 Correct 83 ms 4584 KB Output is correct
4 Correct 79 ms 5408 KB Output is correct
5 Correct 79 ms 5380 KB Output is correct
6 Correct 490 ms 22264 KB Output is correct
7 Correct 502 ms 27216 KB Output is correct
8 Correct 530 ms 27256 KB Output is correct
9 Correct 489 ms 27232 KB Output is correct
10 Correct 488 ms 27260 KB Output is correct