QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#369805 | #8512. Harmonic Operations | willow | WA | 3ms | 10152kb | C++17 | 4.0kb | 2024-03-28 18:07:57 | 2024-03-28 18:07:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 4e5 + 5;
char s[maxn], t[maxn];
int n, k;
int Check(int x) {
for(int i = 1; i <= n; ++ i) {
if(s[i] != s[(i + x - 1) % n + 1]) {
return 0;
}
}
return 1;
}
int sh = -1, g;
struct Arr {
int del, rev, who, cnt[maxn];
void Init(int _who) {
del = rev = 0;
who = _who;
fill(cnt, cnt + maxn, 0);
}
void Reverse() {
rev ^= 1;
who ^= 1;
}
void Left(int w) {
if(rev) {
del += w;
}
else {
del -= w;
}
}
void Right(int w) {
if(rev) {
del -= w;
}
else {
del += w;
}
}
void Add(int x) {
// cerr << "Add delta = " << del << " rev = " << rev << " who = " << who << " x = " << x << endl;
if(rev) {
++ cnt[((-(del + x)) % g + g) % g];
}
else {
++ cnt[((x - del) % g + g) % g];
}
}
int Query() {
int tar = 0;
if(who) {
if(sh == -1)
return 0;
tar = sh;
}
// cerr << "Query tar = " << tar << endl;
if(rev) {
// cerr << "pos = " << (((-(del + tar)) % g + g) % g) << " " << cnt[((-(del + tar)) % g + g) % g] << endl;
return cnt[((-(del + tar)) % g + g) % g];
}
else {
// cerr << "pos = " << (((tar - del) % g + g) % g) << " " << cnt[((tar - del) % g + g) % g] << endl;
return cnt[((tar - del) % g + g) % g];
}
}
}a[2];
char op[5];
int fail[maxn];
main() {
scanf("%s", s + 1);
n = strlen(s + 1);
g = n;
for(int i = 1; i * i <= n; ++ i) {
if(n % i == 0) {
if(Check(i)) {
g = min(g, i);
}
if(Check(n / i)) {
g = min(g, n / i);
}
}
}
for(int i = 1; i <= n; ++ i) {
t[i + n] = t[i] = s[n - i + 1];
}
fail[1] = 0;
int p = 0;
for(int i = 2; i <= n; ++ i) {
while(p && s[i] != s[p + 1])
p = fail[p];
if(s[i] == s[p + 1])
++ p;
fail[i] = p;
}
int now = 0;
for(int i = 1; i <= 2 * n; ++ i) {
while(now && t[i] != s[now + 1])
now = fail[now];
if(t[i] == s[now + 1])
++ now;
// cerr << i << " " << now << endl;
if(now == n) {
sh = i - n;
break;
}
}
// cerr << g << " " << sh << endl;
a[0].Init(0), a[1].Init(1);
scanf("%lld", &k);
long long ans = 0;
for(int i = 1, w; i <= k; ++ i) {
scanf("%s", op + 1);
if(op[1] == 'I') { // reverse
a[0].Reverse();
a[1].Reverse();
if(a[0].who)
a[0].Add(0);
else
a[1].Add(0);
}
else {
scanf("%lld", &w);
if(op[1] == 'L') { // to_left w
a[0].Left(w);
a[1].Left(w);
if(!a[0].who)
a[0].Add(g - w);
else
a[1].Add(g - w);
}
else { // to_right w
a[0].Right(w);
a[1].Right(w);
if(!a[0].who)
a[0].Add(w);
else
a[1].Add(w);
}
}
// cerr << "a[0]: rev = " << a[0].rev << " delta = " << a[0].del << " who = " << a[0].who << ": ";
// for(int i = 0; i < g; ++ i)
// cerr << a[0].cnt[i] << " ";
// cerr << endl;
// cerr << "a[1]: rev = " << a[1].rev << " delta = " << a[1].del << " who = " << a[1].who << ": ";
// for(int i = 0; i < g; ++ i)
// cerr << a[1].cnt[i] << " ";
// cerr << endl;
ans += a[0].Query();
ans += a[1].Query();
// cerr << "? Right = " << i << " ans = " << ans << endl;
}
printf("%lld\n", ans);
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 10064kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 10060kb
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: 10112kb
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: 10060kb
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: 3ms
memory: 10136kb
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: 10000kb
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: 0ms
memory: 10044kb
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: 10140kb
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: 10068kb
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: 3ms
memory: 10036kb
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: 0ms
memory: 10000kb
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: -100
Wrong Answer
time: 0ms
memory: 10152kb
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:
82
result:
wrong answer 1st numbers differ - expected: '75', found: '82'