QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363028#8512. Harmonic Operationsucup-team2303#WA 1ms10128kbC++232.6kb2024-03-23 17:59:212024-03-23 17:59:21

Judging History

你现在查看的是最新测评结果

  • [2024-03-23 17:59:21]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:10128kb
  • [2024-03-23 17:59:21]
  • 提交

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) % 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);
		}
	}
	else S.T = T.T = tmp;

	char o;
	int x, y = 0;
	ll ans = 0;
	rep(i, 1, b) {
		cin >> o;
		// cerr << y << endl;
		y ? T.ins() : S.ins();
		if(o == 'I') {
			S.add(1), T.add(1);
			S.o ^= 1, T.o ^= 1;
			y ^= 1;
		}
		else {
			cin >> x;
			if(o == 'L') x = a - x;
			S.add(x), T.add(x);
		}
		// cout << S.ask() << ' ' << T.ask() << endl;
		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: 8000kb

input:

pda
2
R 2
L 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 10084kb

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: 10064kb

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: 10128kb

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: 1ms
memory: 8080kb

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: 10084kb

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: 7976kb

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: 1ms
memory: 10088kb

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: 1ms
memory: 10084kb

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: 1ms
memory: 8104kb

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: 8060kb

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: 1ms
memory: 10096kb

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:

65

result:

wrong answer 1st numbers differ - expected: '75', found: '65'