| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 827275 |
2023-08-16T10:29:00 Z |
rainboy |
Brperm (RMI20_brperm) |
C |
|
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++)
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
490 ms |
22264 KB |
Output is correct |
| 2 |
Correct |
502 ms |
27216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
