QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#362538#8512. Harmonic Operationsucup-team987#WA 1ms3816kbC++2310.6kb2024-03-23 16:01:402024-03-23 16:01:42

Judging History

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

  • [2024-03-23 16:01:42]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3816kb
  • [2024-03-23 16:01:40]
  • 提交

answer

#if __INCLUDE_LEVEL__ == 0

#include __BASE_FILE__

namespace {

void solve() {
  std::string s;
  scan(s);
  int n = len(s);
  int K;
  scan(K);
  std::vector<int> F(K);
  for (int& e : F) {
    char c;
    scan(c);
    if (c == 'I') {
      e = -1;
    } else if (c == 'L') {
      scan(e);
    } else if (c == 'R') {
      scan(e);
      e = n - e;
    } else {
      assert(false);
    }
  }

  {
    const auto z = atcoder::z_algorithm(s);
    int period = 1;
    while (period < n && period + z[period] < n) {
      ++period;
    }

    n = period;
    s.resize(n);
    for (int& e : F) {
      if (e != -1) {
        e %= n;
      }
    }
  }

  std::basic_string<bool> pref(n + 1, false);
  {
    const auto z = atcoder::z_algorithm(s + std::string(s.rbegin(), s.rend()));
    pref[0] = true;
    for (const int m : rep1(n)) {
      pref[m] = z[n * 2 - m] == m;
    }
  }

  std::basic_string<bool> suff(n + 1, false);
  {
    const auto z = atcoder::z_algorithm(std::string(s.rbegin(), s.rend()) + s);
    suff[n] = true;
    for (const int m : rep(n)) {
      suff[m] = z[n + m] == n - m;
    }
  }

  int m = -1;
  for (const int i : rep(n)) {
    if (pref[i] && suff[i]) {
      assert(m == -1);
      m = i;
    }
  }

  i64 ans = 0;
  if (m == -1) {
    std::map<std::pair<int, int>, int> mp;
    std::pair<int, int> cur{};
    ++mp[cur];
    for (const int e : F) {
      if (e == -1) {
        cur.first ^= 1;
      } else {
        cur.second += e;
        cur.second %= n;
      }
      ans += mp[cur]++;
    }

  } else {
    std::map<std::pair<int, int>, int> mp;
    std::pair<int, int> cur{};
    ++mp[cur];
    for (const int e : F) {
      if (e == -1) {
        cur.first ^= 1;
      } else {
        cur.second += e;
        cur.second %= n;
      }
      auto tmp = cur;
      tmp.first ^= 1;
      tmp.second += n - m;
      tmp.second %= n;
      if (mp.contains(tmp)) {
        ans += mp[tmp];
      }
      ans += mp[cur]++;
    }
  }

  print(ans);
}

}  // namespace

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout << std::setprecision(DBL_DECIMAL_DIG);

  solve();
}

#else  // __INCLUDE_LEVEL__

#include <bits/stdc++.h>

namespace atcoder {

namespace internal {

std::vector<int> sa_naive(const std::vector<int>& s) {
  int n = int(s.size());
  std::vector<int> sa(n);
  std::iota(sa.begin(), sa.end(), 0);
  std::sort(sa.begin(), sa.end(), [&](int l, int r) {
    if (l == r) return false;
    while (l < n && r < n) {
      if (s[l] != s[r]) return s[l] < s[r];
      l++;
      r++;
    }
    return l == n;
  });
  return sa;
}

std::vector<int> sa_doubling(const std::vector<int>& s) {
  int n = int(s.size());
  std::vector<int> sa(n), rnk = s, tmp(n);
  std::iota(sa.begin(), sa.end(), 0);
  for (int k = 1; k < n; k *= 2) {
    auto cmp = [&](int x, int y) {
      if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
      int rx = x + k < n ? rnk[x + k] : -1;
      int ry = y + k < n ? rnk[y + k] : -1;
      return rx < ry;
    };
    std::sort(sa.begin(), sa.end(), cmp);
    tmp[sa[0]] = 0;
    for (int i = 1; i < n; i++) {
      tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
    }
    std::swap(tmp, rnk);
  }
  return sa;
}

template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
std::vector<int> sa_is(const std::vector<int>& s, int upper) {
  int n = int(s.size());
  if (n == 0) return {};
  if (n == 1) return {0};
  if (n == 2) {
    if (s[0] < s[1]) {
      return {0, 1};
    } else {
      return {1, 0};
    }
  }
  if (n < THRESHOLD_NAIVE) {
    return sa_naive(s);
  }
  if (n < THRESHOLD_DOUBLING) {
    return sa_doubling(s);
  }

  std::vector<int> sa(n);
  std::vector<bool> ls(n);
  for (int i = n - 2; i >= 0; i--) {
    ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
  }
  std::vector<int> sum_l(upper + 1), sum_s(upper + 1);
  for (int i = 0; i < n; i++) {
    if (!ls[i]) {
      sum_s[s[i]]++;
    } else {
      sum_l[s[i] + 1]++;
    }
  }
  for (int i = 0; i <= upper; i++) {
    sum_s[i] += sum_l[i];
    if (i < upper) sum_l[i + 1] += sum_s[i];
  }

  auto induce = [&](const std::vector<int>& lms) {
    std::fill(sa.begin(), sa.end(), -1);
    std::vector<int> buf(upper + 1);
    std::copy(sum_s.begin(), sum_s.end(), buf.begin());
    for (auto d : lms) {
      if (d == n) continue;
      sa[buf[s[d]]++] = d;
    }
    std::copy(sum_l.begin(), sum_l.end(), buf.begin());
    sa[buf[s[n - 1]]++] = n - 1;
    for (int i = 0; i < n; i++) {
      int v = sa[i];
      if (v >= 1 && !ls[v - 1]) {
        sa[buf[s[v - 1]]++] = v - 1;
      }
    }
    std::copy(sum_l.begin(), sum_l.end(), buf.begin());
    for (int i = n - 1; i >= 0; i--) {
      int v = sa[i];
      if (v >= 1 && ls[v - 1]) {
        sa[--buf[s[v - 1] + 1]] = v - 1;
      }
    }
  };

  std::vector<int> lms_map(n + 1, -1);
  int m = 0;
  for (int i = 1; i < n; i++) {
    if (!ls[i - 1] && ls[i]) {
      lms_map[i] = m++;
    }
  }
  std::vector<int> lms;
  lms.reserve(m);
  for (int i = 1; i < n; i++) {
    if (!ls[i - 1] && ls[i]) {
      lms.push_back(i);
    }
  }

  induce(lms);

  if (m) {
    std::vector<int> sorted_lms;
    sorted_lms.reserve(m);
    for (int v : sa) {
      if (lms_map[v] != -1) sorted_lms.push_back(v);
    }
    std::vector<int> rec_s(m);
    int rec_upper = 0;
    rec_s[lms_map[sorted_lms[0]]] = 0;
    for (int i = 1; i < m; i++) {
      int l = sorted_lms[i - 1], r = sorted_lms[i];
      int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
      int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
      bool same = true;
      if (end_l - l != end_r - r) {
        same = false;
      } else {
        while (l < end_l) {
          if (s[l] != s[r]) {
            break;
          }
          l++;
          r++;
        }
        if (l == n || s[l] != s[r]) same = false;
      }
      if (!same) rec_upper++;
      rec_s[lms_map[sorted_lms[i]]] = rec_upper;
    }

    auto rec_sa = sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);

    for (int i = 0; i < m; i++) {
      sorted_lms[i] = lms[rec_sa[i]];
    }
    induce(sorted_lms);
  }
  return sa;
}

}  // namespace internal

std::vector<int> suffix_array(const std::vector<int>& s, int upper) {
  assert(0 <= upper);
  for (int d : s) {
    assert(0 <= d && d <= upper);
  }
  auto sa = internal::sa_is(s, upper);
  return sa;
}

template <class T>
std::vector<int> suffix_array(const std::vector<T>& s) {
  int n = int(s.size());
  std::vector<int> idx(n);
  iota(idx.begin(), idx.end(), 0);
  sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
  std::vector<int> s2(n);
  int now = 0;
  for (int i = 0; i < n; i++) {
    if (i && s[idx[i - 1]] != s[idx[i]]) now++;
    s2[idx[i]] = now;
  }
  return internal::sa_is(s2, now);
}

std::vector<int> suffix_array(const std::string& s) {
  int n = int(s.size());
  std::vector<int> s2(n);
  for (int i = 0; i < n; i++) {
    s2[i] = s[i];
  }
  return internal::sa_is(s2, 255);
}

template <class T>
std::vector<int> lcp_array(const std::vector<T>& s, const std::vector<int>& sa) {
  int n = int(s.size());
  assert(n >= 1);
  std::vector<int> rnk(n);
  for (int i = 0; i < n; i++) {
    rnk[sa[i]] = i;
  }
  std::vector<int> lcp(n - 1);
  int h = 0;
  for (int i = 0; i < n; i++) {
    if (h > 0) h--;
    if (rnk[i] == 0) continue;
    int j = sa[rnk[i] - 1];
    for (; j + h < n && i + h < n; h++) {
      if (s[j + h] != s[i + h]) break;
    }
    lcp[rnk[i] - 1] = h;
  }
  return lcp;
}

std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {
  int n = int(s.size());
  std::vector<int> s2(n);
  for (int i = 0; i < n; i++) {
    s2[i] = s[i];
  }
  return lcp_array(s2, sa);
}

template <class T>
std::vector<int> z_algorithm(const std::vector<T>& s) {
  int n = int(s.size());
  if (n == 0) return {};
  std::vector<int> z(n);
  z[0] = 0;
  for (int i = 1, j = 0; i < n; i++) {
    int& k = z[i];
    k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]);
    while (i + k < n && s[k] == s[i + k]) k++;
    if (j + z[j] < i + z[i]) j = i;
  }
  z[0] = n;
  return z;
}

std::vector<int> z_algorithm(const std::string& s) {
  int n = int(s.size());
  std::vector<int> s2(n);
  for (int i = 0; i < n; i++) {
    s2[i] = s[i];
  }
  return z_algorithm(s2);
}

}  // namespace atcoder

template <class T, class U = T>
bool chmin(T& x, U&& y) {
  return y < x && (x = std::forward<U>(y), true);
}

template <class T, class U = T>
bool chmax(T& x, U&& y) {
  return x < y && (x = std::forward<U>(y), true);
}

template <std::signed_integral T = int>
T inf() {
  T ret;
  std::memset(&ret, 0x3f, sizeof(ret));
  return ret;
}

template <std::floating_point T>
T inf() {
  return std::numeric_limits<T>::infinity();
}

template <class T>
concept Range = std::ranges::range<T> && !std::convertible_to<T, std::string_view>;

template <class T>
concept Tuple = std::__is_tuple_like<T>::value && !Range<T>;

namespace std {

istream& operator>>(istream& is, Range auto&& r) {
  for (auto&& e : r) {
    is >> e;
  }
  return is;
}

istream& operator>>(istream& is, Tuple auto&& t) {
  return apply([&](auto&... xs) -> istream& { return (is >> ... >> xs); }, t);
}

ostream& operator<<(ostream& os, Range auto&& r) {
  for (string_view sep = ""; auto&& e : r) {
    os << exchange(sep, " ") << e;
  }
  return os;
}

ostream& operator<<(ostream& os, Tuple auto&& t) {
  const auto f = [&](auto&... xs) -> ostream& {
    [[maybe_unused]] string_view sep = "";
    ((os << exchange(sep, " ") << xs), ...);
    return os;
  };
  return apply(f, t);
}

}  // namespace std

void scan(auto&&... xs) { std::cin >> std::tie(xs...); }
void print(auto&&... xs) { std::cout << std::tie(xs...) << '\n'; }

template <class F>
class fix {
 public:
  explicit fix(F f) : f_(std::move(f)) {}

  decltype(auto) operator()(auto&&... xs) const {
    return f_(std::ref(*this), std::forward<decltype(xs)>(xs)...);
  }

 private:
  F f_;
};

inline auto rep(int l, int r) { return std::views::iota(std::min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }

namespace ranges = std::ranges;
namespace views = std::views;

using i64 = std::int64_t;

#define len(...) static_cast<int>(ranges::size(__VA_ARGS__))

#endif  // __INCLUDE_LEVEL__

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

pda
2
R 2
L 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

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

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

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

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

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:

2502

result:

wrong answer 1st numbers differ - expected: '116', found: '2502'