QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372426#8512. Harmonic OperationskarunaWA 1ms3848kbC++201.5kb2024-03-31 13:22:512024-03-31 13:22:52

Judging History

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

  • [2024-03-31 13:22:52]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3848kb
  • [2024-03-31 13:22:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int SZ = 202020;

int n, q, k[SZ], f[SZ], c[2][SZ];
string S;

int cyclic(string S, string T) {
	S = S + S;

	int n = S.size();
	int m = T.size();

	vector<int> F(m);
	for (int i = 1, p = 0; i < m; i++) {
		while (p && T[p] != T[i]) {
			p = F[p - 1];
		}
		if (T[p] == T[i]) F[i] = ++p;
	}

	for (int i = 0, p = 0; i < n; i++) {
		while (p == m || (p && S[i] != T[p])) {
			p = F[p - 1];
		}
		if (S[i] == T[p]) ++p;
		if (p == m) {
			return i + 1 - p;
		}
	}
	return -1;
}
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin >> S;
	n = S.size();

	vector<int> F(n);
	for (int i = 1, p = 0; i < n; i++) {
		while (p && S[p] != S[i]) {
			p = F[p - 1];
		}
		if (S[p] == S[i]) F[i] = ++p;
	}
	int t = n;
	for (int p = n - 1; ; ) {
		if (n % (n - F[p]) == 0) {
			t = n - F[p];
			break;
		}
		else p = F[p - 1];
	}

	string T = S.substr(0, t);
	reverse(T.begin(), T.end());
	int r = cyclic(S.substr(0, t), T);

	cin >> q;

	ll ans = 0;
	c[0][0]++;
	for (int i = 1; i <= q; i++) {
		string K; cin >> K;
		if (K == "R") {
			int x; cin >> x;
			k[i] = (k[i - 1] + x) % t;
			f[i] = f[i - 1];
		}
		else if (K == "L") {
			int x; cin >> x;
			k[i] = (k[i - 1] + n - x) % t;
			f[i] = f[i - 1];
		}
		else {
			k[i] = (t - k[i]) % t;
			f[i] = f[i - 1] ^ 1;
		}
		ans += c[f[i]][k[i]];
		if (r != -1) {
			ans += c[f[i] ^ 1][(r + t - k[i]) % t];
		}
		c[f[i]][k[i]]++;
	}

	cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

input:

pda
2
R 2
L 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

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

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

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: -100
Wrong Answer
time: 0ms
memory: 3844kb

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:

2500

result:

wrong answer 1st numbers differ - expected: '2556', found: '2500'