QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#362877 | #8512. Harmonic Operations | ucup-team2303# | WA | 1ms | 10140kb | C++23 | 2.5kb | 2024-03-23 17:27:08 | 2024-03-23 17:27:09 |
Judging History
answer
// #pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define PB emplace_back
// #define int long long
#define ll long long
#define vi vector<int>
#define siz(a) ((int) ((a).size()))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
void print(vi n) { rep(i, 0, siz(n) - 1) cerr << n[i] << " \n"[i == siz(n) - 1]; }
#define ui unsigned long long
const int N = 2e5, bs = 29;
char s[N + 5];
int a, b, nxt[N + 5], id;
ui pw[N + 5], pre[N + 5], suf[N + 5];
bool is;
vi st;
struct node {
int o, p, q, s[N + 5], t[N + 5], S, T;
void ins() {
++s[p], ++t[q];
}
void add(int n) {
if(!o) p = (p + n) % S, q = (q + n) % T;
else p = (p + n + S) % S, q = (q + n + T) % T;
}
int ask() {
if(!o) return s[p];
else {
if(is) return t[(q + T + 1) % T];
else if(id != -1) return t[(q + T + id) % T];
return 0;
}
}
} S, T;
ui F(int l, int r) {
return !l ? pre[r] : pre[r] - pre[l - 1] * pw[r - l + 1];
}
ui G(int l, int r) {
return suf[l] - suf[r + 1] * pw[r - l + 1];
}
bool ck(int n) {
rep(i, 0, n - 1) if(s[i] != s[n - i - 1]) return 0;
return 1;
}
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> s >> b;
a = strlen(s);
pre[0] = s[0];
rep(i, 1, a - 1) pre[i] = pre[i - 1] * bs + s[i];
per(i, a - 1, 0) suf[i] = suf[i + 1] * bs + s[i];
pw[0] = 1;
rep(i, 1, a) pw[i] = pw[i - 1] * bs;
nxt[0] = -1;
int j = -1;
rep(i, 1, a) {
for(; ~j && s[i] != s[j + 1]; j = nxt[j]);
if(s[i] == s[j + 1]) ++j;
nxt[i] = j;
}
int tmp = a - 1 - nxt[a - 1];
if(a % tmp) tmp = a;
S.S = T.S = tmp;
T.o = 1;
is = ck(tmp);
if(!is) {
S.T = T.T = tmp;
id = -1;
rep(i, 0, tmp - 2) if(F(0, i) == G(0, i) && F(i + 1, tmp - 1) == G(i + 1, tmp - 1)) {
if(id == -1) id = i;
else assert(0);
}
// cerr << id << endl;
}
else S.T = T.T = tmp;
char o;
int x, y = 0;
ll ans = 0;
rep(i, 1, b) {
cin >> o;
y ? T.ins() : S.ins();
if(o == 'I') {
S.o ^= 1, T.o ^= 1;
y ^= 1;
}
else {
cin >> x;
if(o == 'L') x = a - x;
S.add(x), T.add(x);
}
ans += S.ask() + T.ask();
}
cout << ans;
return cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl, 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 10140kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 10008kb
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: 8112kb
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: 8052kb
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: 1ms
memory: 8088kb
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:
2542
result:
wrong answer 1st numbers differ - expected: '2556', found: '2542'