QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#362849 | #8512. Harmonic Operations | ucup-team3215# | WA | 0ms | 3652kb | C++17 | 2.0kb | 2024-03-23 17:21:47 | 2024-03-23 17:21:48 |
Judging History
answer
#include <bits/stdc++.h>
using ll = signed long long int;
#define all(x) (x).begin(), (x).end()
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using namespace std;
using vi = vector<int>;
vi z_func(const string& s) {
int n = s.size();
vi z(n);
int l = 0, r = 0;
for (int i = 1; i < n; ++i) {
if (i < r) {
z[i] = min(r - i - 1, z[i - l]);
}
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
++z[i];
}
if (i + z[i] > r) {
l = i, r = i + z[i];
}
}
return z;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
string s;
cin >> s;
vi z = z_func(s);
int n = s.size(), period = n;
for (int i = 1; i < n; ++i) {
if (n % i == 0 && i + z[i] == n) {
period = i;
break;
}
}
string p(s.begin(), s.begin() + period);
string pr(p.rbegin(), p.rend());
int x = -1;
vi z2 = z_func(p + "$" + pr + pr);
for (int i = period + 1; i < z2.size(); ++i) {
if (z2[i] == period) {
x = i - period - 1;
break;
}
}
int q;
cin >> q;
vector<map<int, int>> cnt(2);
cnt[0][0] = 1;
int pref = 0;
bool flag = 0;
ll ans = 0;
while (q--) {
char c;
cin >> c;
if (c == 'I') {
flag ^= 1;
} else {
int d;
cin >> d;
pref += (flag ^ (c == 'R') ? 1 : -1) * d;
pref %= period;
if (pref < 0) {
pref += period;
}
}
if (cnt[flag].count(pref)) {
ans += cnt[flag][pref];
}
if (x != -1) {
int di = (x - pref) % period;
if (di < 0) {
di += period;
}
if (cnt[flag ^ 1].count(di)) {
ans += cnt[flag ^ 1][di];
}
}
++cnt[flag][pref];
}
cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3652kb
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: 3580kb
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: 3576kb
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: 0
Accepted
time: 0ms
memory: 3640kb
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:
2556
result:
ok 1 number(s): "2556"
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3584kb
input:
rtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtr 100 R 27 R 68 I L 29 L 51 L 19 L 12 L 10 L 52 L 38 L 17 R 30 L 29 L 51 L 17 R 29 I R 96 R 50 R 56 I I I L 73 L 15 I R 1 R 81 L 94 R 27 R 52 R 57 R 44 I I L 53 I R 87 L 39 L 25 I I R 25 I I I L 88 L ...
output:
58
result:
wrong answer 1st numbers differ - expected: '116', found: '58'