QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#724243 | #8512. Harmonic Operations | ikaurov | WA | 0ms | 3644kb | C++14 | 1.5kb | 2024-11-08 11:14:34 | 2024-11-08 11:14:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'
vector<int> z_function(string s){
int n = sz(s);
vector<int> z(n);
int l = 0, r = 0;
for (int i = 1; i < n; i++){
if (i < r) z[i] = min(z[i - l], r - i);
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 nextocc(string s, string t, int start_idx){
auto z = z_function(s + t);
for (int i = sz(s) + start_idx; i < sz(z); i++){
if (z[i] >= sz(s)) return i - sz(s);
}
return sz(t);
}
const int N = 2e5 + 20;
int cnt[N][2];
int need[2];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
// cout.precision(20);
string s, rs;
cin >> s;
rs = s;
reverse(all(rs));
int p = nextocc(s, s + s, 1);
need[0] = 0, need[1] = 2 * p - 1 - nextocc(s, rs + rs, 0);
int n, x = 0, d = +1;
cin >> n;
ll ans = 0;
cnt[0][0] = 1;
while (n--){
char type;
int off;
cin >> type;
if (type == 'I'){
x -= d, d *= -1;
}
else{
cin >> off;
x += (type == 'L'? +1 : -1) * d * off;
}
x %= p;
if (x < 0) x += p;
if (need[d == -1] >= 0) ans += cnt[(x + p - need[d == -1]) % p][0];
if (need[d == 1] >= 0) ans += cnt[(x + need[d == 1]) % p][1];
cnt[x][d == -1]++;
}
cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3644kb
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: 3548kb
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: 3496kb
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: 3492kb
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: 3540kb
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:
-7239208318
result:
wrong answer 1st numbers differ - expected: '116', found: '-7239208318'