QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379998 | #8512. Harmonic Operations | ucup-team004# | WA | 0ms | 3812kb | C++20 | 2.2kb | 2024-04-06 20:28:50 | 2024-04-06 20:28:50 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
struct G {
int k = 1;
int b = 0;
};
int N;
G operator*(G a, G b) {
return {a.k * b.k, ((a.b * b.k + b.b) % N + N) % N};
}
std::vector<int> manacher(std::string s) {
std::string t = "#";
for (auto c : s) {
t += c;
t += '#';
}
int n = t.size();
std::vector<int> r(n);
for (int i = 0, j = 0; i < n; i++) {
if (2 * j - i >= 0 && j + r[j] > i) {
r[i] = std::min(r[2 * j - i], j + r[j] - i);
}
while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
r[i] += 1;
}
if (i + r[i] > j + r[j]) {
j = i;
}
}
return r;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string S;
std::cin >> S;
N = S.size();
std::vector<int> f(N + 1);
for (int i = 1, j = 0; i < N; i++) {
while (j && S[i] != S[j]) {
j = f[j];
}
j += (S[i] == S[j]);
f[i + 1] = j;
}
if (f[N] % (N - f[N]) == 0) {
N = N - f[N];
S.resize(N);
}
int axis = -1;
auto r = manacher(S);
for (int i = 0; i < N; i++) {
if (r[i + i + N] > N) {
axis = i;
break;
}
}
int K;
std::cin >> K;
std::vector<G> a(K);
for (int i = 0; i < K; i++) {
char x;
std::cin >> x;
if (x == 'I') {
a[i] = {-1, 0};
} else {
int y;
std::cin >> y;
a[i] = {1, (x == 'L' ? (N - y % N) % N : y % N)};
}
}
std::vector<G> pre(K + 1);
pre[0] = {1, 0};
for (int i = 0; i < K; i++) {
pre[i + 1] = pre[i] * a[i];
}
i64 ans = 0;
std::vector cnt(2, std::vector<int>(N));
for (int i = K; i >= 0; i--) {
auto v = pre[i];
ans += cnt[v.k == -1][v.b];
if (axis != -1) {
v = v * G{-1, 2 * axis % N};
ans += cnt[v.k == -1][v.b];
}
cnt[pre[i].k == -1][pre[i].b]++;
}
std::cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3784kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
aaa 4 R 1 I I R 1
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
caso 6 L 1 I I R 1 I I
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq 100 L 12 I R 47 L 54 I I R 80 L 86 L 19 R 5 L 53 L 40 R 20 L 11 R 40 I I R 66 R 6 L 76 L 93 R 39 I I L 24 R 59 R 99 L 52 I I R 77 L 11 R 60 L 16 I L 40 I R 35 L 64 R 11 L 34 I R 35 I L 87 I I L 42 L ...
output:
5050
result:
ok 1 number(s): "5050"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3812kb
input:
wewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewe 100 R 83 R 34 I I R 87 R 74 L 98 I L 77 L 8 R 23 L 94 I I L 79 L 87 L 47 L 85 L 49 L 7 I I R 97 R 15 I R 66 L 8 R 62 R 68 I I R 32 R 24 R 36 L 60 R 75 R 77 I L 42 I L 61 I I R 78 R 51 L 98 I L 77 I I...
output:
1295
result:
wrong answer 1st numbers differ - expected: '2556', found: '1295'