QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#724243#8512. Harmonic OperationsikaurovWA 0ms3644kbC++141.5kb2024-11-08 11:14:342024-11-08 11:14:35

Judging History

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

  • [2024-11-08 11:14:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3644kb
  • [2024-11-08 11:14:34]
  • 提交

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'