QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363618 | #8512. Harmonic Operations | Georgia Tech: Days of Future Past (Jingbang Chen, Yu Gao)# | WA | 24ms | 6916kb | C++23 | 4.1kb | 2024-03-24 00:59:28 | 2024-03-24 00:59:29 |
Judging History
answer
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
typedef long long LL;
typedef unsigned long long ULL;
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define pb push_back
typedef double D;
const int N = 200011;
int tp[N], d[N], nxt[N];
pair<string, int> find(string s) {
int i, j, k, l, n = s.length();
s += s;
for(i = 0, j = 1; j < n; ) {
for(k = 0; k < n && s[i + k] == s[j + k]; k++);
if(k >= n) break;
if(s[i + k] < s[j + k]) {
j += k + 1;
}
else l = i + k, i = j, j = max(l, j) + 1;
}
return make_pair(s.substr(i, n), i);
}
struct Op {
int coe, delta;
void print() const {
printf("c = %d, d = %d\n", coe, delta);
}
};
int per;
Op operator + (const Op & a, const Op & b) {
return Op{a.coe * b.coe, (a.delta * b.coe % per + b.delta + per) % per};
}
bool operator < (const Op & a, const Op & b) {
return a.coe < b.coe || a.coe == b.coe && a.delta < b.delta;
}
int main() {
string s;
cin >> s;
int n = s.size();
int k;
scanf("%d", &k);
for(int i = 0; i < k; i++) {
static char st[11];
scanf("%s", st);
tp[i] = st[0];
//printf("tp[%d] = %c\n", i, tp[i]);
if(tp[i] != 'I') {
scanf("%d", &d[i]);
if(tp[i] == 'L') {
d[i] = d[i] % n;
}else {
d[i] = (-d[i] + n) % n;
}
}
}
int revdelta = -1;
string t = s;
reverse(all(t));
pair<string, int> ms = find(s), mt = find(t);
if(ms.first == mt.first) {
revdelta = ms.se - mt.se;
}
s = '$' + s;
nxt[0] = -1;
for(int i = 1; i <= n; i++) {
int p = nxt[i - 1];
while(p != -1 && s[p + 1] != s[i]) {
//printf("p = %d\n", p);
p = nxt[p];
}
nxt[i] = p + 1;
}
per = n - nxt[n];
if(n % per != 0) {
per = n;
}
LL ans = 0;
//printf("per = %d, revdelta = %d\n", per, revdelta);
if(revdelta == -1) {
Op cur{1, 0};
map<Op, int> cnt;
cnt[cur] = 1;
for(int i = 0; i < k; i++) {
Op opi;
if(tp[i] == 'I') {
opi = Op{-1, 0};
} else {
opi = Op{1, d[i] % per};
}
cur = cur + opi;
//cur.print();
ans += cnt[cur];
cnt[cur]++;
}
/*for(int i = 0, j; i < k; i = j) {
if(tp[i] == 'I') {
j = i + 1;
continue;
}
for(j = i; tp[j] != 'I'; j++);
map<int, int> cnt;
cnt[0] = 1;
int cur = 0;
for(int k = i; k < j; k++) {
cur = (cur + d[k]) % per;
ans += cnt[cur];
cnt[cur]++;
}
}*/
} else {
/*if(per == 1) {
ans = (k * (k + 1ll) / 2);
} else */
/*{
map<int, int> cnt;
cnt[0] = 1;
int cur = 0;
for(int i = 0; i < k; i++) {
if(tp[i] == 'I') {
cur = (per - cur + revdelta) % per;
} else {
cur = (cur + d[i]) % per;
}
ans += cnt[cur];
cnt[cur]++;
}
}*/
Op cur{1, 0};
map<Op, int> cnt;
cnt[cur] = 1;
revdelta %= per;
for(int i = 0; i < k; i++) {
Op opi;
if(tp[i] == 'I') {
opi = Op{-1, revdelta};
} else {
opi = Op{1, d[i] % per};
}
cur = cur + opi;
//cur.print();
//cur.print();
ans += cnt[cur];
//printf("ans = %d\n",ans);
ans += cnt[Op{-cur.coe, (per - cur.delta) % per}];
//printf("ans = %d\n",ans);
cnt[cur]++;
}
}
printf("%lld\n", ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
aaa 4 R 1 I I R 1
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5836kb
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: 3796kb
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: 3884kb
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: 0
Accepted
time: 0ms
memory: 3796kb
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:
116
result:
ok 1 number(s): "116"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5916kb
input:
tcldtcldtcldtcldtcldtcldtcldtcldtcld 100 L 20 I I I L 20 R 13 L 16 L 19 R 10 I I I L 11 R 30 R 30 I L 35 I L 28 R 23 R 24 L 20 R 15 I I L 13 I R 1 I R 6 I I L 22 I L 22 R 22 L 30 L 30 I I I R 35 I R 3 L 1 R 4 I R 11 R 2 R 21 R 15 I R 5 L 2 L 4 L 7 L 19 L 29 R 8 I L 24 I I I L 29 I R 35 R 32 I R 14 L...
output:
703
result:
ok 1 number(s): "703"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
wflbkhwflbkhwflbkhwflbkhwflbkhwflbkh 100 I R 28 R 13 R 7 R 29 I I I R 25 R 10 R 23 I R 26 I I L 18 I R 18 L 6 I I R 8 R 8 I R 6 L 16 I R 2 R 17 L 31 R 31 L 22 R 26 L 21 L 20 R 10 L 13 R 33 R 13 R 35 R 22 L 2 L 4 R 19 L 32 L 25 I L 31 R 10 R 17 R 15 L 6 L 9 R 31 R 20 I I R 4 I L 30 L 30 L 2 R 18 R 35...
output:
442
result:
ok 1 number(s): "442"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
mzgaokjwpmzgaokjwpmzgaokjwpmzgaokjwp 100 R 10 I L 24 L 8 I L 19 L 25 I I R 27 R 24 I I L 16 I I L 35 R 14 I L 23 R 17 R 16 R 4 R 4 L 29 I R 11 R 9 R 15 I L 18 I I L 25 R 13 L 24 I I L 8 I I I I L 24 I I L 19 L 23 I L 20 R 35 L 31 I I R 27 I I I L 35 R 16 L 10 R 28 R 14 I I R 30 R 18 L 16 L 6 L 12 R ...
output:
280
result:
ok 1 number(s): "280"
Test #10:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
gtvcymjngzntgtvcymjngzntgtvcymjngznt 100 L 33 L 5 R 31 R 18 I R 14 R 9 L 1 I R 1 R 15 L 15 I I I L 13 R 7 I I L 2 I L 3 I L 19 L 22 L 2 R 32 I L 1 R 24 R 23 I R 25 L 11 R 34 R 25 I L 25 R 22 R 34 I I L 2 R 13 L 3 I L 30 I R 7 R 20 I R 24 L 34 R 23 I L 26 R 22 I I I R 17 I I L 14 R 27 R 35 I L 34 L 3...
output:
206
result:
ok 1 number(s): "206"
Test #11:
score: 0
Accepted
time: 1ms
memory: 4056kb
input:
dvaauyemcqhrmduoumdvaauyemcqhrmduoum 100 L 21 R 12 R 30 L 13 I I L 1 L 31 R 4 L 20 I L 6 I L 29 R 19 L 12 R 25 R 25 I R 21 I L 12 L 25 R 35 L 8 R 7 R 29 I R 4 L 24 R 29 I I I L 12 L 24 R 19 L 33 L 4 I R 35 I R 16 I R 10 I R 18 R 7 L 33 I I R 22 L 16 L 7 L 20 R 32 I I R 27 I L 9 R 16 I I R 32 I R 1 L...
output:
180
result:
ok 1 number(s): "180"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
pkmsckbnjeeojagpdtfxlmlgofbrygcuqiahynrwooxgdruurdgxoowrnyhaiqucgyrbfoglmlxftdpgajoeejnbkcsmkplhxxhl 100 L 14 R 54 L 88 L 66 L 38 R 91 I I I I R 56 L 4 L 76 R 12 L 86 I I I I R 52 L 98 L 98 L 39 R 60 L 14 R 23 R 92 R 99 L 71 I I I I L 1 R 33 I R 65 L 72 I I I R 20 R 48 L 81 L 7 I R 72 R 14 I I R 10 ...
output:
75
result:
ok 1 number(s): "75"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
txgcggvgarkkflejgkaukutnsjogrglpdmocuhyiboientoffaaaffotneiobiyhucomdplgrgojsntukuakgjelfkkragvggcgxt 100 R 35 R 84 I R 68 R 24 L 42 L 24 R 16 R 80 R 95 L 9 L 26 L 96 R 64 I R 56 I L 5 R 83 R 2 R 57 R 28 I R 17 I R 11 I R 100 L 42 I L 89 I L 91 I I R 78 I R 30 L 6 I L 56 L 48 R 79 L 8 I R 5 L 25 R 2...
output:
76
result:
ok 1 number(s): "76"
Test #14:
score: 0
Accepted
time: 0ms
memory: 4088kb
input:
qhygenaiejhluibjfyjbdoslylsodbjyfjbiulhjeianegyhqydgoxbmbcuslmfqgraeqkpuerbnbreupkqeargqfmlsucbmbxogdy 100 L 41 R 73 R 41 I R 59 R 77 I I R 21 L 5 R 30 R 3 L 94 I L 36 R 2 R 85 L 39 L 17 R 47 I R 86 L 30 R 38 R 80 I R 39 I I L 99 I L 15 I L 76 L 68 L 91 I R 71 R 36 L 14 L 15 I L 63 R 71 I L 38 I R 3...
output:
48
result:
ok 1 number(s): "48"
Test #15:
score: 0
Accepted
time: 19ms
memory: 6916kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
20000100000
result:
ok 1 number(s): "20000100000"
Test #16:
score: 0
Accepted
time: 24ms
memory: 6912kb
input:
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...
output:
20000100000
result:
ok 1 number(s): "20000100000"
Test #17:
score: 0
Accepted
time: 14ms
memory: 6900kb
input:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
20000100000
result:
ok 1 number(s): "20000100000"
Test #18:
score: -100
Wrong Answer
time: 19ms
memory: 6892kb
input:
opopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopopop...
output:
4999995412
result:
wrong answer 1st numbers differ - expected: '10000007832', found: '4999995412'