QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#107428#6505. CCPC StringmaspyAC ✓33ms4196kbC++2316.1kb2023-05-21 13:23:022023-05-21 13:23:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-21 13:23:29]
  • 评测
  • 测评结果:AC
  • 用时:33ms
  • 内存:4196kb
  • [2023-05-21 13:23:02]
  • 提交

answer

#line 1 "library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;

template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'000'000'000;
template <>
constexpr ll infty<ll> = ll(infty<int>) * infty<int> * 2;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * infty<ll>;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;

using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define vv(type, name, h, ...) \
  vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...)   \
  vector<vector<vector<type>>> name( \
      h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...)       \
  vector<vector<vector<vector<type>>>> name( \
      a, vector<vector<vector<type>>>(       \
             b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))

// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)

#define FOR_subset(t, s) \
  for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second

#define stoi stoll

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T, typename U>
T ceil(T x, U y) {
  return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U>
T floor(T x, U y) {
  return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T, typename U>
pair<T, T> divmod(T x, U y) {
  T q = floor(x, y);
  return {q, x - q * y};
}

template <typename T, typename U>
T SUM(const vector<U> &A) {
  T sum = 0;
  for (auto &&a: A) sum += a;
  return sum;
}

#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) \
  sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()

template <typename T>
T POP(deque<T> &que) {
  T a = que.front();
  que.pop_front();
  return a;
}
template <typename T>
T POP(pq<T> &que) {
  T a = que.top();
  que.pop();
  return a;
}
template <typename T>
T POP(pqg<T> &que) {
  assert(!que.empty());
  T a = que.top();
  que.pop();
  return a;
}
template <typename T>
T POP(vc<T> &que) {
  assert(!que.empty());
  T a = que.back();
  que.pop_back();
  return a;
}

template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
  if (check_ok) assert(check(ok));
  while (abs(ok - ng) > 1) {
    auto x = (ng + ok) / 2;
    tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
  }
  return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
  FOR(iter) {
    double x = (ok + ng) / 2;
    tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
  }
  return (ok + ng) / 2;
}

template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}

// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
  vc<int> A(S.size());
  FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
  return A;
}

template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
  int N = A.size();
  vector<T> B(N + 1);
  FOR(i, N) { B[i + 1] = B[i] + A[i]; }
  if (off == 0) B.erase(B.begin());
  return B;
}

// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
  vector<int> ids(len(A));
  iota(all(ids), 0);
  sort(all(ids),
       [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
  return ids;
}

// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
  vc<T> B(len(I));
  FOR(i, len(I)) B[i] = A[I[i]];
  return B;
}
#endif
#line 1 "library/other/io.hpp"
// based on yosupo's fastio
#include <unistd.h>

namespace fastio {
#define FASTIO
// クラスが read(), print() を持っているかを判定するメタ関数
struct has_write_impl {
  template <class T>
  static auto check(T &&x) -> decltype(x.write(), std::true_type{});

  template <class T>
  static auto check(...) -> std::false_type;
};

template <class T>
class has_write : public decltype(has_write_impl::check<T>(std::declval<T>())) {
};

struct has_read_impl {
  template <class T>
  static auto check(T &&x) -> decltype(x.read(), std::true_type{});

  template <class T>
  static auto check(...) -> std::false_type;
};

template <class T>
class has_read : public decltype(has_read_impl::check<T>(std::declval<T>())) {};

struct Scanner {
  FILE *fp;
  char line[(1 << 15) + 1];
  size_t st = 0, ed = 0;
  void reread() {
    memmove(line, line + st, ed - st);
    ed -= st;
    st = 0;
    ed += fread(line + ed, 1, (1 << 15) - ed, fp);
    line[ed] = '\0';
  }
  bool succ() {
    while (true) {
      if (st == ed) {
        reread();
        if (st == ed) return false;
      }
      while (st != ed && isspace(line[st])) st++;
      if (st != ed) break;
    }
    if (ed - st <= 50) {
      bool sep = false;
      for (size_t i = st; i < ed; i++) {
        if (isspace(line[i])) {
          sep = true;
          break;
        }
      }
      if (!sep) reread();
    }
    return true;
  }
  template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
  bool read_single(T &ref) {
    if (!succ()) return false;
    while (true) {
      size_t sz = 0;
      while (st + sz < ed && !isspace(line[st + sz])) sz++;
      ref.append(line + st, sz);
      st += sz;
      if (!sz || st != ed) break;
      reread();
    }
    return true;
  }
  template <class T, enable_if_t<is_integral<T>::value, int> = 0>
  bool read_single(T &ref) {
    if (!succ()) return false;
    bool neg = false;
    if (line[st] == '-') {
      neg = true;
      st++;
    }
    ref = T(0);
    while (isdigit(line[st])) { ref = 10 * ref + (line[st++] & 0xf); }
    if (neg) ref = -ref;
    return true;
  }
  template <typename T,
            typename enable_if<has_read<T>::value>::type * = nullptr>
  inline bool read_single(T &x) {
    x.read();
    return true;
  }
  bool read_single(double &ref) {
    string s;
    if (!read_single(s)) return false;
    ref = std::stod(s);
    return true;
  }
  bool read_single(char &ref) {
    string s;
    if (!read_single(s) || s.size() != 1) return false;
    ref = s[0];
    return true;
  }
  template <class T>
  bool read_single(vector<T> &ref) {
    for (auto &d: ref) {
      if (!read_single(d)) return false;
    }
    return true;
  }
  template <class T, class U>
  bool read_single(pair<T, U> &p) {
    return (read_single(p.first) && read_single(p.second));
  }
  template <size_t N = 0, typename T>
  void read_single_tuple(T &t) {
    if constexpr (N < std::tuple_size<T>::value) {
      auto &x = std::get<N>(t);
      read_single(x);
      read_single_tuple<N + 1>(t);
    }
  }
  template <class... T>
  bool read_single(tuple<T...> &tpl) {
    read_single_tuple(tpl);
    return true;
  }
  void read() {}
  template <class H, class... T>
  void read(H &h, T &... t) {
    bool f = read_single(h);
    assert(f);
    read(t...);
  }
  Scanner(FILE *fp) : fp(fp) {}
};

struct Printer {
  Printer(FILE *_fp) : fp(_fp) {}
  ~Printer() { flush(); }

  static constexpr size_t SIZE = 1 << 15;
  FILE *fp;
  char line[SIZE], small[50];
  size_t pos = 0;
  void flush() {
    fwrite(line, 1, pos, fp);
    pos = 0;
  }
  void write(const char val) {
    if (pos == SIZE) flush();
    line[pos++] = val;
  }
  template <class T, enable_if_t<is_integral<T>::value, int> = 0>
  void write(T val) {
    if (pos > (1 << 15) - 50) flush();
    if (val == 0) {
      write('0');
      return;
    }
    if (val < 0) {
      write('-');
      val = -val; // todo min
    }
    size_t len = 0;
    while (val) {
      small[len++] = char(0x30 | (val % 10));
      val /= 10;
    }
    for (size_t i = 0; i < len; i++) { line[pos + i] = small[len - 1 - i]; }
    pos += len;
  }
  void write(const string s) {
    for (char c: s) write(c);
  }
  void write(const char *s) {
    size_t len = strlen(s);
    for (size_t i = 0; i < len; i++) write(s[i]);
  }
  void write(const double x) {
    ostringstream oss;
    oss << fixed << setprecision(15) << x;
    string s = oss.str();
    write(s);
  }
  void write(const long double x) {
    ostringstream oss;
    oss << fixed << setprecision(15) << x;
    string s = oss.str();
    write(s);
  }
  template <typename T,
            typename enable_if<has_write<T>::value>::type * = nullptr>
  inline void write(T x) {
    x.write();
  }
  template <class T>
  void write(const vector<T> val) {
    auto n = val.size();
    for (size_t i = 0; i < n; i++) {
      if (i) write(' ');
      write(val[i]);
    }
  }
  template <class T, class U>
  void write(const pair<T, U> val) {
    write(val.first);
    write(' ');
    write(val.second);
  }
  template <size_t N = 0, typename T>
  void write_tuple(const T t) {
    if constexpr (N < std::tuple_size<T>::value) {
      if constexpr (N > 0) { write(' '); }
      const auto x = std::get<N>(t);
      write(x);
      write_tuple<N + 1>(t);
    }
  }
  template <class... T>
  bool write(tuple<T...> tpl) {
    write_tuple(tpl);
    return true;
  }
  template <class T, size_t S>
  void write(const array<T, S> val) {
    auto n = val.size();
    for (size_t i = 0; i < n; i++) {
      if (i) write(' ');
      write(val[i]);
    }
  }
  void write(i128 val) {
    string s;
    bool negative = 0;
    if (val < 0) {
      negative = 1;
      val = -val;
    }
    while (val) {
      s += '0' + int(val % 10);
      val /= 10;
    }
    if (negative) s += "-";
    reverse(all(s));
    if (len(s) == 0) s = "0";
    write(s);
  }
};
Scanner scanner = Scanner(stdin);
Printer printer = Printer(stdout);
void flush() { printer.flush(); }
void print() { printer.write('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
  printer.write(head);
  if (sizeof...(Tail)) printer.write(' ');
  print(forward<Tail>(tail)...);
}

void read() {}
template <class Head, class... Tail>
void read(Head &head, Tail &... tail) {
  scanner.read(head);
  read(tail...);
}
} // namespace fastio
using fastio::print;
using fastio::flush;
using fastio::read;

#define INT(...)   \
  int __VA_ARGS__; \
  read(__VA_ARGS__)
#define LL(...)   \
  ll __VA_ARGS__; \
  read(__VA_ARGS__)
#define STR(...)      \
  string __VA_ARGS__; \
  read(__VA_ARGS__)
#define CHAR(...)   \
  char __VA_ARGS__; \
  read(__VA_ARGS__)
#define DBL(...)      \
  double __VA_ARGS__; \
  read(__VA_ARGS__)

#define VEC(type, name, size) \
  vector<type> name(size);    \
  read(name)
#define VV(type, name, h, w)                     \
  vector<vector<type>> name(h, vector<type>(w)); \
  read(name)

void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 1 "library/ds/fastset.hpp"
/* 64分木。
insert, erase
[]での存在判定
next, prev
*/
struct FastSet {
  using uint = unsigned;
  using ull = unsigned long long;

  int bsr(ull x) { return 63 - __builtin_clzll(x); }
  int bsf(ull x) { return __builtin_ctzll(x); }

  static constexpr uint B = 64;
  int n, lg;
  vector<vector<ull>> seg;
  FastSet(int _n) : n(_n) {
    do {
      seg.push_back(vector<ull>((_n + B - 1) / B));
      _n = (_n + B - 1) / B;
    } while (_n > 1);
    lg = int(seg.size());
  }
  bool operator[](int i) const { return (seg[0][i / B] >> (i % B) & 1) != 0; }
  void insert(int i) {
    for (int h = 0; h < lg; h++) {
      seg[h][i / B] |= 1ULL << (i % B);
      i /= B;
    }
  }
  void add(int i) { insert(i); }
  void erase(int i) {
    for (int h = 0; h < lg; h++) {
      seg[h][i / B] &= ~(1ULL << (i % B));
      if (seg[h][i / B]) break;
      i /= B;
    }
  }
  void remove(int i) { insert(i); }

  // x以上最小の要素を返す。存在しなければ n。
  int next(int i) {
    chmax(i, 0);
    if (i >= n) return n;
    for (int h = 0; h < lg; h++) {
      if (i / B == seg[h].size()) break;
      ull d = seg[h][i / B] >> (i % B);
      if (!d) {
        i = i / B + 1;
        continue;
      }
      // find
      i += bsf(d);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += bsf(seg[g][i / B]);
      }
      return i;
    }
    return n;
  }

  // x以下最大の要素を返す。存在しなければ -1。
  int prev(int i) {
    if (i < 0) return -1;
    if (i >= n) i = n - 1;
    for (int h = 0; h < lg; h++) {
      if (i == -1) break;
      ull d = seg[h][i / B] << (63 - i % 64);
      if (!d) {
        i = i / B - 1;
        continue;
      }
      // find
      i += bsr(d) - (B - 1);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += bsr(seg[g][i / B]);
      }
      return i;
    }
    return -1;
  }

  // [l, r)
  template <typename F>
  void enumerate(int l, int r, F f) {
    int x = l - 1;
    while (1) {
      x = next(x + 1);
      if (x >= r) break;
      f(x);
    }
  }

  void debug() {
    string s;
    for (int i = 0; i < n; ++i) s += ((*this)[i] ? '1' : '0');
    print(s);
  }
};
#line 4 "main.cpp"

void solve() {
  STR(S);
  ll N = len(S);
  FastSet ss(N);
  FOR(i, N) if (S[i] == 'p') ss.insert(i);

  ll ANS = 0;

  FOR(i, N) {
    if (S[i] == 'c') continue;
    int a = ss.prev(i - 1) + 1;
    int b = ss.next(i + 1) - 1;
    ll x = i - a;
    ll y = b - i;
    x = min(x / 2, y);
    ANS += x;
  }
  print(ANS);
}

signed main() {
  INT(T);
  FOR(T) solve();
  return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3424kb

input:

5
?cpc
ccp??
???c???
?c???cp??
?c?????cccp????

output:

1
1
4
5
14

result:

ok 5 number(s): "1 1 4 5 14"

Test #2:

score: 0
Accepted
time: 31ms
memory: 3580kb

input:

100000
c?cp?pp?c?
ppp????pcc
c?ppppcc?p
?p?cc?ccpc
pc?ppc?cp?
?pp?p?c?cp
p???pcccpp
cpcccpcc??
????c?cc?p
pcp?pppcp?
cc?pccc?pp
cpc??c?p?c
??c??cpppc
cpcp?pc??c
pcc??ppccp
?p?p?cpcpp
c?ccpcpp??
ppc?cccccp
cp?pcccppp
cccc???ccc
c?pcc?pp?p
pcc?p??cp?
?cc??ppp?p
?ppp??p?pp
??pccc??p?
???cccpp??
c???c?p...

output:

1
3
0
2
1
1
1
2
4
0
1
3
2
1
1
1
1
0
0
7
1
2
1
1
3
1
3
1
2
2
2
3
0
2
1
8
0
3
2
0
1
1
1
1
1
0
3
0
3
3
2
1
4
0
1
1
1
1
2
1
6
4
3
1
4
1
2
1
1
0
1
2
5
1
1
3
2
1
1
2
1
5
0
0
2
1
3
1
2
0
4
0
0
1
5
2
0
1
0
1
0
0
1
0
1
2
0
0
0
0
3
0
0
2
1
3
2
4
2
0
1
3
1
3
1
3
2
1
2
0
1
2
0
0
5
0
4
4
0
0
2
3
0
1
1
0
1
0
1
1
...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 26ms
memory: 3540kb

input:

100000
???pp??c??
p??pcccp??
p?pp??cc??
p????pp???
?c?ppp????
?pp???pcp?
???????c??
c?p?p?c?pp
??c?cpp?pc
pc?ccp??p?
p????p?pc?
pppcc??cp?
c??cpp????
?pc?p?p???
??cp?p????
?ppppccp??
????c???cc
c?c?cp???p
??c??c?p?c
p?p?pp??p?
?pc??pp???
pcc??pcpcc
??p?cc?p??
?c???c????
p?c?cp??p?
??c???pc?c
?p?c?c?...

output:

1
2
1
1
1
1
10
1
1
3
2
3
2
1
2
1
9
3
5
1
0
2
3
10
4
5
3
3
2
0
8
1
1
1
4
3
3
7
3
7
2
3
4
8
1
3
7
2
10
0
6
1
7
0
1
3
2
6
10
2
5
4
6
4
1
3
5
3
1
2
9
0
2
1
2
7
4
2
10
4
9
5
6
3
3
4
3
0
4
6
4
5
1
4
3
5
2
3
7
2
9
3
3
3
2
4
5
3
3
5
4
6
1
1
12
9
3
3
2
9
5
5
5
9
3
3
5
3
2
4
4
0
3
4
2
5
0
1
4
3
4
5
3
2
6
7
5
...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 21ms
memory: 3488kb

input:

10000
ccp?pc?cp?cp??ppcc??ccp?cppcpc???cccccp??cp?pcppcp?c??pcppcpc??pc?pcppppccpp?pppcp?pcp?p?c?c????cccc
p???ccppccc?p?????ccp?c?p?ppcccpcp??c?cppccc?cp???pc?p?pc?cppp?pp?ppc?c???cc?ccp?p???pp?pccp?cc??cc?
ccccp?cp?pp?pcc??pc?pc??c??ppp????pccpp?cpccpc?p?pcpppc?pppp?c?ccc?cpc?cpcp????pp?ppccp?pccp...

output:

28
30
26
23
23
26
23
25
26
20
32
28
34
19
29
13
12
30
19
38
32
22
31
25
29
32
34
29
28
17
27
61
16
16
29
12
42
36
15
13
18
27
15
20
28
23
38
38
34
35
30
25
27
43
31
26
20
23
45
41
87
25
27
25
32
21
35
19
35
21
17
20
26
45
32
21
23
23
35
24
12
24
29
33
35
19
21
20
30
16
26
13
27
24
28
27
37
19
24
25
...

result:

ok 10000 numbers

Test #5:

score: 0
Accepted
time: 19ms
memory: 3464kb

input:

1000
??pp??pcpp?ccp??pp?ppcpc?c???pcpcp?cccpppc?c?ppc?p?pcc??cccc??cppc?pc???ppp?p?p?ppccp?cpcc?cpc?pcp?c??c?pc??cp?cpcp?pc?p?cpccc??cccc??c??cpcccc??ccppc??pc?ppp??ppccp??c?ppp?ppccpcpc?cccp?pccpc?pc?ccppc?pcppccc??c??????cpp?pp?c?pp?ccccp?pc??cc?cpcpcpp???ccpcp?cccp?pp?ccc?ppccccp??????c?cc??c?ccp...

output:

290
280
266
279
289
304
385
292
242
316
245
245
247
253
254
390
297
279
277
267
254
280
267
347
237
264
333
262
285
285
267
236
249
294
327
305
266
274
258
259
260
313
278
271
272
261
296
219
254
282
296
257
231
250
251
293
315
261
289
302
286
231
277
302
263
262
260
290
251
294
247
243
320
344
318
...

result:

ok 1000 numbers

Test #6:

score: 0
Accepted
time: 19ms
memory: 3436kb

input:

1000
?????????????????????????????????p??????????????????????????????????????????p??????????????????????????????????????????????????????????????p????????????cp?????????????????????????????????????????????????????????????????????????????c???????????????????????????????????????????????????????????????...

output:

24795
38683
43374
40572
19397
29397
33629
25374
34988
27882
30805
17920
19482
28640
36088
23120
22234
29923
40073
32290
23138
19252
19047
31091
20720
13892
35194
28153
16235
95681
17487
30610
34861
31112
22008
14669
17720
21254
20388
63985
26402
25313
21735
36330
43267
39793
32223
41635
26991
23431
...

result:

ok 1000 numbers

Test #7:

score: 0
Accepted
time: 15ms
memory: 3516kb

input:

1000
??p???????????????????????????????????????????????p????????????????????????????????????????????????????c??????c??????????c????????????????????????????????????????????????c??????c???c?????????????????????????????????????????????c????c??????c????????????????c???????c???c??????????????????????????...

output:

38431
50325
40041
38642
54638
51644
65061
80024
50145
77187
99305
29692
55661
49128
67468
48058
47507
53684
58318
54057
33448
78524
37534
43797
40568
34123
31270
60175
75099
55714
28945
36047
42956
31432
51861
23652
79716
112982
71348
55645
32387
60564
37551
34998
34530
30474
41652
62836
47828
25220...

result:

ok 1000 numbers

Test #8:

score: 0
Accepted
time: 19ms
memory: 3692kb

input:

10
?ccccpcccccp?pcccccccccc?cpccpccc??p?ccpppp?ccppcpcppcccppp?cc?cccccccc?ccppcccpcccccpccpcpccccccccc?cc?ccc??ccccpccppccp?cccc??ccppccppc?c?c??c??c?cccppcccc?c?c?cpcccccpp???cpcccc???cp?c?cppccp?cc?cpc?cpcpcccc?cccpcc?ccccccpcpcpc?cccccc?p?cccpp?c?cc?c?cc?ccccc?cc?p?cccccc??pcc??cpcccccccccc?pcpc...

output:

42231
42138
42281
42162
42482
41938
41573
42083
41475
42371

result:

ok 10 numbers

Test #9:

score: 0
Accepted
time: 15ms
memory: 3636kb

input:

10
?????????cc????ccpc?cpcc?c?p??c??pccc?c?c?pcc?cp?c???c????c????p??cp?p???c??c?????cccc?c????c?p???????c???c???p???ccpc?pcp????ccc?c?ccc?pp????c????c?c?????cp?c???ccc??cpp???c??c????c??cp???c?c??c???pc?????p?pc??c???????c?????????ccp?cc???c??cp?c?c??????????c???cc?c?cc?c?ccc??cc???c??ppc?p????c???...

output:

312649
315623
329566
326145
324504
314751
316618
327125
324448
325388

result:

ok 10 numbers

Test #10:

score: 0
Accepted
time: 20ms
memory: 3536kb

input:

10
?????c??c?p?????????????????????????????????????c??p??????c????????????c????????c??????c??????????????c????????????????????c????????????????????????????????????????????????????cc????????c??????????????????????????????c??????????????c?????????????????????p?????????????????c????????????????????????...

output:

3180953
3158086
3225555
3247694
3154314
3067404
3408500
3409083
3152234
2978500

result:

ok 10 numbers

Test #11:

score: 0
Accepted
time: 21ms
memory: 3548kb

input:

10
??????????c?????????c??c??cc???????????????????????????????c?????????????c???cc??????????????????????????????c?c????????????c???c????c??????????????????????????????????????????????????????????c??????????????c???c???????????????????????????c??c???c?????????????????c?????????????c??????????????????...

output:

13813001
14231919
12197068
13517413
15160453
12978964
14364247
13085948
11982623
13986192

result:

ok 10 numbers

Test #12:

score: 0
Accepted
time: 24ms
memory: 3592kb

input:

10
?????????????????????c??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????c???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????c...

output:

68377390
51809363
49002027
80746342
67179859
61714157
70861287
64561751
71701475
58590962

result:

ok 10 numbers

Test #13:

score: 0
Accepted
time: 22ms
memory: 3520kb

input:

10
???????????????????????????????????????????????????????????????????????????????????????????????????????????????p??????????????????????????????????????????????p?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????p????????????????...

output:

17126493
16475514
15919867
15632069
17718479
17057494
18599151
18637215
18480240
17874538

result:

ok 10 numbers

Test #14:

score: 0
Accepted
time: 17ms
memory: 4156kb

input:

1
ppccccpcpcccppccpppccpcppcppcccpcccpcpppccpppcpccppcccpcppcccpccppcpcccpcppcpppcppccpccpppccpccccpcppcppcpppppcppccccccpccppppppppcpppppcppppppppcpccccpccpcpppcppppcpcpccpcppccppccppcpcccpccpccpccppcppcccppcpccccppcpcppccppppcpppppppcpcpccpcppppcpccppppcppcpcccccppccpcppcpccpppcpccpccpcppccpppcccc...

output:

71002

result:

ok 1 number(s): "71002"

Test #15:

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

input:

1
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccpccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

329115

result:

ok 1 number(s): "329115"

Test #16:

score: 0
Accepted
time: 8ms
memory: 4168kb

input:

1
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

362774

result:

ok 1 number(s): "362774"

Test #17:

score: 0
Accepted
time: 17ms
memory: 4160kb

input:

1
cccpccpppppccppccccppcpppcppcppppcppccppcpccpppcppcppcppcppppppppppppcpcpppppppppcppppppppppccppcpcpppppppppppppccppcccpppcccccpppcccppppppppppccpppcpppccppppcpcpcpppcccccpcpppppccppppppcpcpccppcppcppcpcpccppcppcpcppppcpppppppcppppcpccccpcppccpcppcpppppcpcccccpcccpppppppcpppcpppppcppcpppcppccccpcp...

output:

25452

result:

ok 1 number(s): "25452"

Test #18:

score: 0
Accepted
time: 18ms
memory: 4192kb

input:

1
ppppppppppppppppppppppppppppppppppppppppppppppppppcpppppppppppppppppppppppppcpppppppppppppppppppppppppcpppppppppppppppppppppppppppppppppppppppppcppppppppppppppppppppppppppcpppppppppppppppppppppppppppcpppppppppppppppppppppppppppppppppppppppppppppcpppppppppppppppppppppppppcpppppppppppppppppppppppppp...

output:

92

result:

ok 1 number(s): "92"

Test #19:

score: 0
Accepted
time: 20ms
memory: 4072kb

input:

1
c?ccc??pppc??ppppcp?cpcp??ccpp?cc?c??cc?pcccppppc?p??cp?c???p?cp?cppcppcccp??p??cp?cp?cc?p?ppc??c??cc??p?c?p?p?c?p?c?c?p?p??pp?pppcp?ppppccc?p?pppcppccp?pcpc?c?ppppcpp?pc??????ccccpcp??c?cpppc???ppcpcppc????cpc???pc???ccppcpcpppc?pccpcpccccppc?c?pc?cc?c?cc?ppc??p?cpp???p?c?pcp??cpcp??ccppcp?p???c?...

output:

279203

result:

ok 1 number(s): "279203"

Test #20:

score: 0
Accepted
time: 7ms
memory: 4156kb

input:

1
ccccccccccccccpccccccc?ccccccccccccpcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc?cccccccccccccccccccccccccccccccccccccccccccccccccccccpccc?ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

673994

result:

ok 1 number(s): "673994"

Test #21:

score: 0
Accepted
time: 7ms
memory: 4120kb

input:

1
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

683455

result:

ok 1 number(s): "683455"

Test #22:

score: 0
Accepted
time: 14ms
memory: 4112kb

input:

1
pppppc??pp??cc??pcppcpp?pp?cpcpccppppp?p?pc?cppcppppcccpppp?p??c?ppcppppp?ppp?ccpppcpppcpppp?pccpccp?ccppcp???cccpcp?ppppcc?p????pp?p?c?pcpcpppp?pc??ppp?p?cpccp?pccpcp?cc?p?ppc?cp?cpppp?ccpcp??p?ccpcp??ppppppcp??pc?cp?p?pcc?ppc?ppcp?ppcc?pp?p?pppppp?cpppc?pcpp?pp?pp?pcccp?p??p?p?cpccpcp?ppp?ccccc?...

output:

107185

result:

ok 1 number(s): "107185"

Test #23:

score: 0
Accepted
time: 24ms
memory: 4168kb

input:

1
ppppppppppppppp?ppppppppppp?ppppcppppppppcpcppppp?ppppppp?ppc?pppppppcpppppppppppp?ppppppp?pppppppcpppppppppppppppppppppcppcppppcppcppppcppppppppppcppppppppppp??pppppp?ppp?ppppp?pppppp?ppppp?ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppcpppppppppppp...

output:

708

result:

ok 1 number(s): "708"

Test #24:

score: 0
Accepted
time: 17ms
memory: 4104kb

input:

1
???????p??????????????????????????????????????????????????????????????????????????????????????????????????????????????????c????????????????????????????????????????????????????p???????????????????????????????????????????????????????????????????????????????????????????c??????????????????????????????...

output:

31783930

result:

ok 1 number(s): "31783930"

Test #25:

score: 0
Accepted
time: 12ms
memory: 4188kb

input:

1
?ccccccccccccccc?c?????cc?c?cc??c?cc?cc?cc?cc?cc??cccc?c?ccccccc??ccccc?cc?c?cccccccccccc?cc??c?cccc??c??c?c?c?cc?cc?cccccccc?cc??c?c??ccccc??ccccc??ccc??ccccc??c??c?c?ccc??cccc???cccc??cccccccccc?cc???c?????ccccc?c?cc?c??ccc?cc?cccc?cc?c?ccc?c?ccc?c??cc?cc?ccccccc?c?c?c??c??ccc?cc?ccc??ccc?ccc?cc...

output:

33861597

result:

ok 1 number(s): "33861597"

Test #26:

score: 0
Accepted
time: 6ms
memory: 4144kb

input:

1
ccccc?cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc?ccccccccccccccccccccccccccccccc?cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc?cccccccccccccccccccccccccccccccccccccccccccccccccccccccc?ccccccccccccccccccccccccccccccccccccccccc...

output:

34477192

result:

ok 1 number(s): "34477192"

Test #27:

score: 0
Accepted
time: 23ms
memory: 4076kb

input:

1
p????????????????????????????????????????????????????????????????????p????????????????????????????????????????????????????????????????????????????????p?p???p??????????????????????????????????????????????????????????????????????????????????????????????????????????????p?????????????????p????????????...

output:

16238624

result:

ok 1 number(s): "16238624"

Test #28:

score: 0
Accepted
time: 17ms
memory: 4188kb

input:

1
?????????p???p????????ppp????ppp???????????p??????pp?????p???p?????????????pp?????????p???????????p?pp???p?????????????p??????????????????ppp??p?p?p???p????p?????p???p?????????p???p?p?????????????p??????????????????????????p??p????p?p??????p???????????p???p?p?pp??????c?p???????????p??p????p?p?????...

output:

1379358

result:

ok 1 number(s): "1379358"

Test #29:

score: 0
Accepted
time: 33ms
memory: 4172kb

input:

1
??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

1693438123

result:

ok 1 number(s): "1693438123"

Test #30:

score: 0
Accepted
time: 23ms
memory: 4140kb

input:

1
c??c??????????????c?????????????????c??????????????????????????????????????c????????????????????????c???????????????????????????????????????????c???????????c???????????????????????????????????????????c???????c??????????????????????????c????????????????????????????????????????c?????c???????????????...

output:

1635530918

result:

ok 1 number(s): "1635530918"

Test #31:

score: 0
Accepted
time: 19ms
memory: 4128kb

input:

1
cc??c?????ccc??ccc??cccc??cc??ccc?c?cccc??c?cc??c?????cc???c????c?cccccc?c?cc??c??c?c?c???c????cccc??c?cc??c???c?c??cc?ccc?c?????ccc?c??cc?c????c?c?c???ccc?c??cc???c?c?c?cccc?c?c??????c?c?cc?????c?c?ccc??cc??c????cccccccc??????cc?c?cccc?c?c???cc?cc??c????cc???cccccc?c??c??c???????c???cc???ccccc??c...

output:

1565712044

result:

ok 1 number(s): "1565712044"

Test #32:

score: 0
Accepted
time: 25ms
memory: 4068kb

input:

1
??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

857766882

result:

ok 1 number(s): "857766882"

Test #33:

score: 0
Accepted
time: 22ms
memory: 4036kb

input:

1
??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

83528239

result:

ok 1 number(s): "83528239"

Test #34:

score: 0
Accepted
time: 30ms
memory: 4124kb

input:

1
??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

13682413748

result:

ok 1 number(s): "13682413748"

Test #35:

score: 0
Accepted
time: 29ms
memory: 4104kb

input:

1
???????????????????????????????????????????????c?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????c????????????????????????????????????????????????????????????????????????????????????...

output:

11230990743

result:

ok 1 number(s): "11230990743"

Test #36:

score: 0
Accepted
time: 19ms
memory: 4128kb

input:

1
c?????c????c????????????????????cc??????????????c????????c???????c???c???c?????????c?c????????c?c?????cc???????????????c????????????c??c????cc???c???????cc??c?????????????c??????c?c???c????c????c????c??c??c????c??c??c??????????c???????????c???????c??c??ccc????c?????????c????????c????????c?????????...

output:

8649736098

result:

ok 1 number(s): "8649736098"

Test #37:

score: 0
Accepted
time: 23ms
memory: 4140kb

input:

1
??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

4822437338

result:

ok 1 number(s): "4822437338"

Test #38:

score: 0
Accepted
time: 19ms
memory: 4084kb

input:

1
??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

517209577

result:

ok 1 number(s): "517209577"

Test #39:

score: 0
Accepted
time: 26ms
memory: 4084kb

input:

1
??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

54942716850

result:

ok 1 number(s): "54942716850"

Test #40:

score: 0
Accepted
time: 30ms
memory: 4080kb

input:

1
??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

41657025028

result:

ok 1 number(s): "41657025028"

Test #41:

score: 0
Accepted
time: 28ms
memory: 4188kb

input:

1
????????????cc????????????????c????????????????????????????????????????c????????????????????????c???????????c???????c?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

51698992920

result:

ok 1 number(s): "51698992920"

Test #42:

score: 0
Accepted
time: 26ms
memory: 4128kb

input:

1
??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

18713559228

result:

ok 1 number(s): "18713559228"

Test #43:

score: 0
Accepted
time: 23ms
memory: 4112kb

input:

1
??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

2424737782

result:

ok 1 number(s): "2424737782"

Test #44:

score: 0
Accepted
time: 25ms
memory: 4196kb

input:

1
??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

166666166667

result:

ok 1 number(s): "166666166667"