QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#19059	#2113. Zbalansowane słowa	Elegia	10 ✓	186ms	116852kb	C++17	3.5kb	2022-01-27 21:35:06	2022-09-06 08:15:41

Judging History

This is the latest submission verdict.

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-09-06 08:15:41]
Judged

Verdict: 10
Time: 186ms
Memory: 116852kb

Show

[2022-01-27 21:35:06]
Submitted

answer

/*
_/_/_/_/    _/_/_/_/_/  _/_/_/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/  _/  _/
_/      _/  _/  _/    _/    _/_/
_/_/_/_/      _/_/     _/_/_/_/_/

_/_/_/_/    _/    _/  _/      _/
_/      _/   _/  _/   _/_/  _/_/
_/      _/    _/_/    _/ _/_/ _/
_/      _/     _/     _/  _/  _/
_/      _/    _/_/    _/      _/
_/      _/   _/  _/   _/      _/
_/_/_/_/    _/    _/  _/      _/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/
*/
#include <cassert>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <vector>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int _ = 300005;

ull base[26];
int ord[_][26], dro[26], cnt[26];
char s[_];

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  for (int i = 0; i != 26; ++i) base[i] = rng();
  ull B = rng();

  cin >> (s + 1);
  int N = strlen(s + 1);
  memset(ord[0], -1, sizeof(ord[0]));
  ull hsh = 0;
  for (int i = 1; i <= N; ++i) {
    hsh += base[s[i] - 'a']; ++cnt[s[i] - 'a'];
    memcpy(ord[i], ord[i - 1], sizeof(ord[i]));
    int pos = 0; while (ord[i][pos] != s[i] - 'a' && ord[i][pos] != -1) ++pos;
    ord[i][pos] = s[i] - 'a';
    rotate(ord[i], ord[i] + pos, ord[i] + pos + 1);
  }
  memset(dro, -1, sizeof(dro));
  unordered_map<ull, int> mp; mp.reserve(N * 26);
  ull ans = 0;
  for (int i = N; i; --i) {
    int myn = 26, mask = 0; ull bmask = 0;
    for (int j = 0; j != 26; ++j) {
      if (ord[i][j] == -1) break;
      myn = min(myn, ord[i][j]);
      mask |= 1 << ord[i][j];
      bmask += base[ord[i][j]];
      ull v = hsh - cnt[myn] * bmask + B * mask;
      ++mp[v];
    }
    hsh -= base[s[i] - 'a']; --cnt[s[i] - 'a'];
    int pos = 0; while (dro[pos] != -1 && dro[pos] != s[i] - 'a') ++pos;
    dro[pos] = s[i] - 'a'; rotate(dro, dro + pos, dro + pos + 1);
    mask = bmask = 0; myn = 26;
    for (int j = 0; j != 26; ++j) {
      if (dro[j] == -1) break;
      myn = min(myn, dro[j]);
      mask |= 1 << dro[j]; bmask += base[dro[j]];
      ull v = hsh - cnt[myn] * bmask + B * mask;
      ans += mp[v];
    }
  }
  cout << ans << '\n';

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}

源文件, 语言: C++17

詳細信息

Subtask #1:

score: 1

Accepted

Test #1:

score: 1

Accepted

time: 2ms

memory: 3756kb

input:

aabbabcccba

output:

result:

ok single line: '28'

Test #2:

score: 0

Accepted

time: 1ms

memory: 3596kb

input:

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 2ms

memory: 3600kb

input:

bc

output:

result:

ok single line: '3'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3604kb

input:

bbc

output:

result:

ok single line: '5'

Test #5:

score: 0

Accepted

time: 2ms

memory: 3600kb

input:

bcaab

output:

result:

ok single line: '10'

Test #6:

score: 0

Accepted

time: 2ms

memory: 3600kb

input:

ccaccaacaa

output:

result:

ok single line: '27'

Test #7:

score: 0

Accepted

time: 2ms

memory: 3588kb

input:

bcabaabbcbacbaccccbc

output:

result:

ok single line: '57'

Test #8:

score: 0

Accepted

time: 2ms

memory: 3552kb

input:

aaabaaababbaaaabaabb

output:

result:

ok single line: '54'

Test #9:

score: 0

Accepted

time: 2ms

memory: 3692kb

input:

cccccccccccccccccccc

output:

result:

ok single line: '210'

Test #10:

score: 0

Accepted

time: 2ms

memory: 3776kb

input:

bacacbabccbacabbcabb

output:

result:

ok single line: '70'

Test #11:

score: 0

Accepted

time: 2ms

memory: 3616kb

input:

bccaabbaccbaabcacbab

output:

result:

ok single line: '68'

Test #12:

score: 0

Accepted

time: 2ms

memory: 3612kb

input:

abbcccaaaabbbbbccccc

output:

result:

ok single line: '65'

Subtask #2:

score: 1

Accepted

Test #13:

score: 1

Accepted

time: 2ms

memory: 3792kb

input:

aabbbacbcbbcabababbaaacaaabccabcaaaabccabcbbbcbabaaabaacacbcccabccaacbbcacabbbaaaaaaaabccaabbabcaaa

output:

result:

ok single line: '326'

Test #14:

score: 0

Accepted

time: 2ms

memory: 3644kb

input:

cccbcaabccbbcaaaabcbbacccbcbaacbabcacbaccababcabcabaaacbccbaacbcbbabaccabcaaababccbbbcaccabbaacbacba

output:

result:

ok single line: '513'

Test #15:

score: 0

Accepted

time: 2ms

memory: 3636kb

input:

cababccabbacbacbcaabcabccbacbabacabccbacbacabacbcbacbaacbabcbcacbaacbcabcbaabcabcbaccabbacbcabacbacc

output:

result:

ok single line: '1125'

Test #16:

score: 0

Accepted

time: 2ms

memory: 3728kb

input:

caacacabaabbbbccbccaabbccbabccbbcbbaaabacaaccbcbcaaccbbaacbaccbbacacbbaaabcbcacababbcacaaccbcbcabbab

output:

result:

ok single line: '506'

Test #17:

score: 0

Accepted

time: 2ms

memory: 3800kb

input:

abbcccaaaabbbbbccccccaaaaaaabbbbbbbbcccccccccaaaaaaaaaabbbbbbbbbbbccccccccccccaaaaaaaaaaaaabbbbbbbbb

output:

result:

ok single line: '587'

Subtask #3:

score: 1

Accepted

Test #18:

score: 1

Accepted

time: 1ms

memory: 3724kb

input:

cbbbaaccbaaccbbcacaaccabcaaccccbbbaacabcbcabcaccbbbcaacbcbccccbbbcaaaacbacacbaababbbbcbaaaccbcabbccc

output:

result:

ok single line: '330'

Test #19:

score: 0

Accepted

time: 1ms

memory: 3720kb

input:

aaabcbbcabacabaaacacbcbcbbacabbaaaaaabbacbacbbbbbcbaabcabcacbaabccbaacabccccbbabaaccbbabbbbbbcabbabc

output:

result:

ok single line: '340'

Test #20:

score: 0

Accepted

time: 2ms

memory: 3636kb

input:

bcabacccbababaacbcbbcaacabccbabbaccacacabbbacbaccbcababaccbcabbacacbaaabccacbbacbaabcaccbbbcabaacbcb

output:

result:

ok single line: '726'

Test #21:

score: 0

Accepted

time: 2ms

memory: 3644kb

input:

bacabcacbbaaccbbccbaabbccaacbacabbcabcacbabbaacaacbbccbaaccbcabcbbcababcacaacbacbbcaabbccaacbabcacba

output:

result:

ok single line: '764'

Subtask #4:

score: 1

Accepted

Test #22:

score: 1

Accepted

time: 4ms

memory: 4232kb

input:

cacabacbcbccbbbbcaccaabcabbbabbcccccccaccaccbacbaabbbcabccaccccaacabaabcacaccbcbcacbcabacccbccccbabbbcacababcbacaccbabccbacbbaaabccbaabcaaaabcaaacacbacabcabcabcabaaaccbbbcacacbbaaacaababaacacbacabcbcaabcbcabbaabcbccabaacaacaacaaacccaabbcaacabaaaccbcbabcbaccababbcbccbaccbbbcbcaaacbccbcabccabcaaaabbbb...

output:

result:

ok single line: '12577'

Test #23:

score: 0

Accepted

time: 3ms

memory: 4172kb

input:

accbcbccccbcbbbaccbbbcccaccabccabccbcbcbcbbbacabaabaaabccacccbccacacacbbbbcccbababaacabaaccbccaccaaabbacbcbbbbababbbcccaaaabbbbbaacacbcaaccacacbcabcaccbbcaabaaccaacacaccabbbccccacacaccccabbcaabaacaacaabcacbccccaaacacbcbbaccaabcabcbbcaacbbcaccbbbaabbabaabbbcaccbaaaccbcabbbbcbaccccbbbbaaababaccacbbbba...

output:

result:

ok single line: '11845'

Test #24:

score: 0

Accepted

time: 2ms

memory: 4176kb

input:

cabcbaabcabccbacababcacbabcbacbcabacbacacbbacabcbacbcacababccababccbacabcbabcaacbacbbcacbabacbcabaccbacabacbabcbaccababccababcabcbcabacbcaabcbaccabcbacbaabcacbbcacbaacbabcbcabaccabbaccabcababccbabaccabacbcbaabcacbacbbcaacbbacbaccabbcacbacababcabcacbacbcabbcabacbcaabcabcbacbcaabcbcacababcabcacbabccab...

output:

result:

ok single line: '839557'

Test #25:

score: 0

Accepted

time: 2ms

memory: 4228kb

input:

babababaabbcbccbcbbcccacaacacababcaccababcbcaacabbcbaccaabbcababbabababbbbccbcccacaacaccacacaccaaccccbbbbcaabaabbbacbabaababbbbaaaccaacaacccabcccbbbbcbccbcccbbbcbcbabbaaaabbaaccaccaacaacaccaaacccaabbabaabbabbbcccccbcbbbbacabacbcbcabacbabbabaaaabbabbacccbbbbbcbbccccbaacacaccacacaccaacbbaaccbaacccaccb...

output:

result:

ok single line: '116531'

Test #26:

score: 0

Accepted

time: 3ms

memory: 4228kb

input:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

result:

ok single line: '2253000'

Test #27:

score: 0

Accepted

time: 3ms

memory: 4304kb

input:

abbcccaaaabbbbbccccccaaaaaaabbbbbbbbcccccccccaaaaaaaaaabbbbbbbbbbbccccccccccccaaaaaaaaaaaaabbbbbbbbbbbbbbcccccccccccccccaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbccccccccccccccccccaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccc...

output:

result:

ok single line: '81775'

Subtask #5:

score: 1

Accepted

Test #28:

score: 1

Accepted

time: 3ms

memory: 4204kb

input:

ccaaababaabcacacccaaabacaaabaacbcbaabacbcccccbcabcbcccaacbcacbbbcaaaabbcacabbbaacacbabbcaaabbbabcbaabbcbbcccbccaabaccbabccabccacbcbccababcaaabbbbbaacabbbcccccabaaaaacbaabbccccaacbabcbaaaaccbabccaabbaaaabbabbcccacbabcacaaacbacacccacbacacbbbbacbacaabbbcacbaabcababcbabbbaaaabaabaaacabbcccbabbbbbccabcac...

output:

result:

ok single line: '12094'

Test #29:

score: 0

Accepted

time: 3ms

memory: 4228kb

input:

abcbaacaaacabaaacaaaccaabaaaccbcabaabcbcbabbbbcaaabcccccccacabbbcbcbbbaaacaaaaababcccaacbbabcccbbcbacababcbcbaacbbbbcbbcacbcbcaabbaababacccbabccaabcaabccbabccbcaccabbbababbbcabbaacabaaabacbacabbccccccbbccbaccbbbcbbbabbacabccaabbcaaccbaaaaabaacbcbbacbbcbaaabcbbbcaaaaaabccaabccabaabaaaaacbccbbcccbccab...

output:

result:

ok single line: '12080'

Test #30:

score: 0

Accepted

time: 3ms

memory: 4308kb

input:

ccaaacbcbbabaccbabaaaaccbabaabcccabbacbabbaabbbaccccbbcaccbccabbaccbcbcaacbababacbcccaabbabbcbbaccaabcababbabbcccaaccaccaabcacaccabacbbcbababbcaabbccaaaabcccbbcbbcaacbbacabacabccbabbccacbcbabacaabbabaaccbcbcbccababbccbcababcaaaaccbbccaaaabaccbbccabaccaabbcaacbacbababccbccbbabaacbacbcabcaacbbababccab...

output:

result:

ok single line: '146615'

Test #31:

score: 0

Accepted

time: 3ms

memory: 4376kb

input:

acbcabcabbccaabacacbccbababbaabcacabbccacbcbaacbbacbcabcbcaccababacabababccbbcacabcabcacabbcababcacbaccbcaabcabacbcbabcacabcabcabcabcaabbccbaabaccbcabbcabacbacbacbacccaaababcbbccbbacaacbababbcbcccaaabccbacbbacacbabaccbacabacbcbaccaacbcbbbaabcabcaabcabcabbcacccbbbbaacaaccababcacbabcabcabcccaaccbbbaba...

output:

result:

ok single line: '460919'

Test #32:

score: 0

Accepted

time: 3ms

memory: 4340kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

result:

ok single line: '1503501'

Subtask #6:

score: 1

Accepted

Test #33:

score: 1

Accepted

time: 10ms

memory: 14680kb

input:

cbbcbacbbaacabcbabcccaccabbcbbbaccccbbccccabcacabacbbcbacacbcacbbcccbbbabbbabbbbacbacabcacabacbaccacaabaaacababaccbbbbccacbabbacabaabbbaaaabcccacccbabbbbacbbcbbbcbbcaacbccaccaaaccbabccbabbacbacbbcacbccbcaacbbbbbccccbaacacabbababaabacbcacbcaacbcacbbbbcbbacbbaaabaaabacbabbccbaccacbbbccacbcccccabbbaaba...

output:

result:

ok single line: '135289'

Test #34:

score: 0

Accepted

time: 9ms

memory: 14524kb

input:

ccbabbcbaacacaabaaaaabbbaabcbaaabcaababbbaacbcaaaaabaaacbcaaaabcccbbacbcccaacccabcccbbcaaaababccaacbbaaabacbbacaccabaaaccbbcccaabbaaccbabccbacbcbaccbbacababcabbacbbbbaabbaabcccababbabaabcbcbbabcbabaaacacbcabbcaccbbcaaccaccccbabbabacccccbcaaabbcccabccacbaaaccccacbbbcbcacaacbcbabcccaccccbbbcabbacabcac...

output:

result:

ok single line: '177090'

Test #35:

score: 0

Accepted

time: 10ms

memory: 14408kb

input:

acaaccbbbaacacacaaccbabcacccaabbbccbbbccccbaccbccbbccccccbcaababbacccbcabcabbaacbbcccaaababacacccaccaababcbaabcbaacabacbbbabbbaaccbcacbbcaacbbcbbbcccbcbbcbcaababccacbaacccbccacabaabbaaaaabccaaaaaaaacbbbcbcaaabccaabbabbcabbccacbbbbcbabbcabcaabcbaaacbbacbacaacbacabccacbbbbbacbbbbaaabccabacbaaacbacbccc...

output:

result:

ok single line: '836606'

Test #36:

score: 0

Accepted

time: 11ms

memory: 14072kb

input:

aabbababaaaaaabaababbbbabbbbaabbabbaabaaaccccccaaaaccacaaacacaaaaaccccacaccccbbbbcbbcccccbcbccbcbcccbcccbbcbbbcbbbbabababbabaaaaabbabbaabaaabbbbbbbbaabbababbaaaabbabbbbaaaabaabaaaabbbaaaaabababbabbabaaabbabaaabbbababaabbababbabbbbaaabaabbbaccbbbbccccbccbbbbcbcccccbccccbbccbbbbcbbbcbbccbbbbbbcbcbcbcc...

output:

result:

ok single line: '383649'

Test #37:

score: 0

Accepted

time: 3ms

memory: 12888kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

450015000

result:

ok single line: '450015000'

Test #38:

score: 0

Accepted

time: 18ms

memory: 14788kb

input:

abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc...

output:

149805209

result:

ok single line: '149805209'

Test #39:

score: 0

Accepted

time: 7ms

memory: 13312kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

225030000

result:

ok single line: '225030000'

Test #40:

score: 0

Accepted

time: 3ms

memory: 14260kb

input:

cbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcb...

output:

150035001

result:

ok single line: '150035001'

Test #41:

score: 0

Accepted

time: 15ms

memory: 14860kb

input:

abbcccaaaabbbbbccccccaaaaaaabbbbbbbbcccccccccaaaaaaaaaabbbbbbbbbbbccccccccccccaaaaaaaaaaaaabbbbbbbbbbbbbbcccccccccccccccaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbccccccccccccccccccaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccc...

output:

result:

ok single line: '2486841'

Subtask #7:

score: 1

Accepted

Test #42:

score: 1

Accepted

time: 35ms

memory: 40400kb

input:

acacbccaacbabcbbabcbcbbacbabbbbacccacaacbccbcaacaabaacbcabaccaccccaccbacbccccbaaccbccacccaccbabaccabbbbcccabcccbaaabbabbbbbcbbbcabcabbacacaaacccbacbbbcccabaaabcaabcbabbbcbbacaaccacaaabccbbbcccccccabaccaacabcababcbabaacbcbbabaaaccbccccbaabaccaaaabcabbbacaaabbbacbacaaacbacabbacaabcaaaaccbbaccccacbbaac...

output:

result:

ok single line: '540518'

Test #43:

score: 0

Accepted

time: 40ms

memory: 40552kb

input:

bccaacaaccabcccccacbcbbccccbbbcaaacbabbbabbaaccabacbaacacccccabbacaaacbbbaccacccbccbabbacbabbacbcabaabcbacbabcabcacbacbaccaaccbacaabcbaaaaababcbacacacaaaccacacbbbbabccbaacaabcbbcaacccaacbabcbbcbcaaacaababccabbbbccaaacbbbcaabbccacbbaacacbaaccabbbabccbaabcabaaabbccbcaacccacabccbcbcacbcbbbaaaabbaacccca...

output:

result:

ok single line: '515172'

Test #44:

score: 0

Accepted

time: 36ms

memory: 40344kb

input:

bcbabaaccbcbbcbccabccbabbbabaaacbbcbcbcacbbcbcbabccbbccbaaacbaabcaaacbcbbbccacaccbbcabbaaacaaaacacaccacbabcbaaaaacbabcccacabbbacaccacbabbcccbbcbbcbbcbcabacaabababbaaabccaccbbacaccaacaacbbabcbccccbbbcabaacbbcaabbbbacccbcaacaaaacbacbabbccccbabaacacbaabcabbabbabbcccabbbccbcaacaaacccbccacbbacccabbccacab...

output:

result:

ok single line: '512785'

Test #45:

score: 0

Accepted

time: 38ms

memory: 39848kb

input:

bbbabbacaccacabaccbabccabcaaaacccbaaacbbcbbaabbaccbccbbaacbcbcbaacacbaacbcbbcacccbaabababacacbbccbbccacbabbacaaaccacbabbabcaabbacbbacbaccaccbbcacabcabcabcaaacbbcababccabaabcbcabccbacbacbcccbaabaabacbcabcbbcbcabaacccabcaaacbbbcbcaabbccababacacabcbcacbbcaacabbcccbabaabbacbcbcbaacbaacccacaacbbacaabbcbb...

output:

227746038

result:

ok single line: '227746038'

Test #46:

score: 0

Accepted

time: 35ms

memory: 37488kb

input:

bccbbcccbbbccbcbbbccbccbccbccbcbbbccccbbbbcbcbcbabbabbbaaaabaaababbbbbaabbabaaaaaabaabbabbbbbbaaaacaccacaccccaaacaaccacccccacccccccaaaaaaaaaaaacababbaabbbababaababbabaaabcbbcbbccbbbccbbccbcccbccbbaacaacccacccaaacacaccaaaccbcabacacbabcbcaabacbcbbbcbccbbcbbccccbccccbbbaaabbababbabbabaabaaabbbaccaaacac...

output:

14888419

result:

ok single line: '14888419'

Test #47:

score: 0

Accepted

time: 35ms

memory: 36176kb

input:

cccbbccbbbbcbbcbbcccbbbbcbbccbbbcbbbbbccbbccbccbbbcbcbcbccbcccbccbcbbbbcccccbcbbccbbbccbbcbbbcccbccbbcbbbccccbbbbbcccbcbcbbbcbbccbccbcccbcbbbbbcbbbbcbcbbcbccbcbccccbcbbbcccbbbbbcbcbcbbcccbbbbbbcbccbcccccbbcccbbbbbbbcbcccccccbccbbccbccbcbbcbccbbcbcbbbccbcbbcbbcbcbbcbbbcbcbcbcbcccbcccbcbbbbcbcbbbcbbcc...

output:

14243037

result:

ok single line: '14243037'

Test #48:

score: 0

Accepted

time: 18ms

memory: 37868kb

input:

abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...

output:

2499300150

result:

ok single line: '2499300150'

Test #49:

score: 0

Accepted

time: 23ms

memory: 36172kb

input:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

2500100000

result:

ok single line: '2500100000'

Test #50:

score: 0

Accepted

time: 44ms

memory: 40928kb

input:

abbcccaaaabbbbbccccccaaaaaaabbbbbbbbcccccccccaaaaaaaaaabbbbbbbbbbbccccccccccccaaaaaaaaaaaaabbbbbbbbbbbbbbcccccccccccccccaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbccccccccccccccccccaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccc...

output:

15036290

result:

ok single line: '15036290'

Subtask #8:

score: 1

Accepted

Test #51:

score: 1

Accepted

time: 42ms

memory: 40392kb

input:

cacaccaabcccacaaacbbbabacbcbbcabcbccbcaccbcaabbbbccacccbbbbabcabcbacbacccababaabcbaababcaaaabbacbbbbccbaabcbacacbcbaccacbbcabbabbcaacbbcabbabaccacbbbccaabbbbaccccacabbaaaacbbaabacabccaaaacbcabcacabaaaccccbccbbaaabaaaaacaababccbacbbccabbbacccabbbabbbacaaacaaacaccaccaacbbaaaccbabbcccccababbccbabcaabab...

output:

result:

ok single line: '538547'

Test #52:

score: 0

Accepted

time: 40ms

memory: 40556kb

input:

accacbcabcaabaccbaacacacbbabacacbccbaacbbccabbcccbaaabbcbbbabccaacbabaaccabcbaaccacabbcbbabccaccccaaaaaccaacaaccabcaaccabbabacabbbaabacabaacacbacbbbcaacbbbabacbbccbccccbacbccbbbccbaccaaabcaabcbabcaacccbcaaccbababbbaccccababbbcbcbabbccbccaccbbbacaacccccccbbcaccccbccbabbbacbbcacccacbbcabaacacacabcbcaa...

output:

result:

ok single line: '554550'

Test #53:

score: 0

Accepted

time: 45ms

memory: 40392kb

input:

cbbcacaccccbbbabacaabacbaabbcbaacbaabbbcacabccbcbbaaccccabcaaccbcaccbbcacbbcccacbbbbabcbacabbbaabaaabcaaaacacbcababaacabcbcaacbcbcaccaccaabacbacacbbbabcccbcabcaacabcaaccbacbccbbaccbbcabacbcbbabacabbcbccccbccabaaaaabcbbacbabbbccbccaaabacbacabbccccaabbcabacaaccbbcbbacabccbbbcbbaabcabacccbcbaccbbaccbcc...

output:

result:

ok single line: '574809'

Test #54:

score: 0

Accepted

time: 40ms

memory: 39752kb

input:

acabbbcbaacccbccabccbbcaacaabacbacbcaccaabbbcccbabccabbbbcbcaabbbbbcabcabcbbaaabbaabbccccbcabcccaccacccaacbbcabbbcabbaaabbbccaaacabbababaaacbbaccbcacaacaccaccccbabcaaabccbaabacbbaaccaabbaabaaacbbcaacbcbacaaabcbbbcbaabaacbbaaacaacabbaabaaccbbbcccacabcabbbaabbababbccbbbaacacacaaaabcabccabbbbcbbabbcaac...

output:

43845324

result:

ok single line: '43845324'

Test #55:

score: 0

Accepted

time: 31ms

memory: 39164kb

input:

cababccaaaccaaccbabaabbbaabbbbccbcccccbbacacababbcccbbcbbabaababaaaaccccabbbaabcbcbcaccacabacabcbabcaccaacccbbaabbabccbabaabbaabbaccccaaaacabcbbcbcccbbcabaccabcbcaabbbaabacccbbbaacccababaabbcccbbacacaccabcbcaabcabacbbcaababbabaacccaaacbcccbbcbacbabbaabbacccacaaacbcbcbbcabccbacabbbccbcaaacccaabbbaaac...

output:

187147086

result:

ok single line: '187147086'

Test #56:

score: 0

Accepted

time: 13ms

memory: 34536kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

5000050000

result:

ok single line: '5000050000'

Test #57:

score: 0

Accepted

time: 41ms

memory: 40904kb

input:

abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc...

output:

1665783554

result:

ok single line: '1665783554'

Test #58:

score: 0

Accepted

time: 40ms

memory: 39868kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1666783334

result:

ok single line: '1666783334'

Subtask #9:

score: 1

Accepted

Test #59:

score: 1

Accepted

time: 155ms

memory: 115108kb

input:

acabcbaaaaacacbaaabbcccbcabcabcbbcabbcacbabccbcaabaacaabbbbacbacbabaccaccbaababcaccbacaaaccbccaacbbaabcbabccacacbacbcbbbccccbaacbcaacbbaaaabcaccbaaacabbcbaabcbcacbbbbabccbccaacbbccacacbacbcababcbacaaacbcccabbcbbbcaacabcbbcbbcccccaabcbccbccabacbbcccacbaccbbabbcbcbaaabaabcabacacbbbaabcccacbbacbcbccbab...

output:

result:

ok single line: '1598274'

Test #60:

score: 0

Accepted

time: 137ms

memory: 115268kb

input:

aabbccbaacabbabcbabbaabbabbbcabacaaccaaccaaaccacbbbbcbcccacbababaaacaaabcbbcabaabaaacccbacbbcacbcacbacacbaacbacbccbcbbbaacabcaccbcccabcacbccbcccabbbbcabcccccbacccccabccbccbaabbccacabccbbbcaaaacbacbbcaacaaccabcaabacbcaaaabcccabbccaabcccbbccccbccabbabcaacbbbaccbccacaacccbbbbbaaaabcbcccabcacaabcacccbab...

output:

result:

ok single line: '1603805'

Test #61:

score: 0

Accepted

time: 164ms

memory: 115192kb

input:

abaaccabcabcbacabcbbcaacabcabcabcbbabbaccbbbbbbbbccacaaabbccaaaaababbbbacbaccababbaabaccabaacbacaccabacaabcabacbbccabbbcaaaaccaacccabbcccabcabcbabaacacbccaacbbacbacbbacaabcbabaacccccbcabbbaabcabaabcabbaccbbbaabacacbcbbccbabaccbaaaccbcacaccbbabbcbaacccaabcccccbabaacaccaccbbabababaaaaccccabccbcaaabccc...

output:

result:

ok single line: '1536333'

Test #62:

score: 0

Accepted

time: 143ms

memory: 113332kb

input:

bcaabccabcbabacabcacbcbabcbaabaccbcacbabbbbbcacbccaaaacccaabbcacacaabacbbcbaccbbbacaabcbbccbaaaccbbcaabbabaccacabacaccbbbacaaacccbaacaaaccbcabbbccbbbbaabccbabbacccaabbacbcbbbcccaaaccbacbababccbacaababbaaabbbcacccbababccacccbcabacbbbaacabbabcbabcacbaaccacccbabacabcacbacbabccbbbcabaccacccababaccaabbab...

output:

2040070100

result:

ok single line: '2040070100'

Test #63:

score: 0

Accepted

time: 154ms

memory: 112732kb

input:

caaaccaaaabaccbacabcaacacabcbbbbcbcababcababccacabbabbaaaabacccaaabaaacbacabcacaabacbaacccbbcacbbacacbbbcbbbcbccbabccbaabcacabbacccaacaccbbbabbabcabbaaccabaaabcacbabbabaaccbcbbbbbbbcaaabbabccbcaaaaaacbbabbbcabcbbabccabcabababccacbbacaacaccccbcbbbccaaccbbcccbabbbbbbabcccbcbccacbcbacbcabbccbabaccaaaab...

output:

29116193

result:

ok single line: '29116193'

Test #64:

score: 0

Accepted

time: 112ms

memory: 106136kb

input:

bcbaacabccbbcbbaaaaccaccaacaacaccacaccabbbbbbcccccbbcbcccaaababbaaabbbbbbaabbbcbcbcbcbbcccbbbbbcccbccccccbcbcbbccbcbbbcbbcbcbcbccaccccaacaaacaacacacacacccaaccaaccaccacacacaacaacccacaaaabaaabbbaabbaabbaabbaababbbbabbbaaabaababbababbbabaaaabcbcaacbcbacabbbaabacccaaabccbbccbbacacbcbbcbccaaaacccbaabaabb...

output:

130711332

result:

ok single line: '130711332'

Test #65:

score: 0

Accepted

time: 61ms

memory: 102412kb

input:

aaaccacccaacaaaacaaaaccacaaacaaccccccacaaacccaaccaaccaaacaacccaaaaacacaaccaacccacaccaacaaaacaacccaaacaccaacaaaaccaacacaacacccaaaacaaaaccaaacaaccccccacaaccccaccacccccccaaccaccacaaaaaaacccccaacaacaaacaaaaaaacaaaccacacaaacacaaccccacaaaacccccacaaccaacaaaccacacacacccccaaacaaacccaaccaccccaaaacacacacacacac...

output:

94743989

result:

ok single line: '94743989'

Test #66:

score: 0

Accepted

time: 116ms

memory: 107188kb

input:

abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...

output:

22498200091

result:

ok single line: '22498200091'

Test #67:

score: 0

Accepted

time: 76ms

memory: 102440kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

22500300000

result:

ok single line: '22500300000'

Test #68:

score: 0

Accepted

time: 186ms

memory: 116852kb

input:

abbcccaaaabbbbbccccccaaaaaaabbbbbbbbcccccccccaaaaaaaaaabbbbbbbbbbbccccccccccccaaaaaaaaaaaaabbbbbbbbbbbbbbcccccccccccccccaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbccccccccccccccccccaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccc...

output:

77882676

result:

ok single line: '77882676'

Subtask #10:

score: 1

Accepted

Test #69:

score: 1

Accepted

time: 168ms

memory: 115368kb

input:

aabbaaababbcbcbaccbbaabcabcccccbbcbccccabaacccabbbccccabaabbccbbaabbcbaaacacccbbbaabbcaabcbcbaabaaacacaabccacbabacbcbcbbacbbbcccacabaccbcbcbbbbcaccbabbbacbcccccccbabbcbaacabbbabaaaacbcacacbaabbcbbcbabaacbaabccbcabbabbbbbaaaaaacaacaccacccbaaacabcbbaaaabaccabbabacbbbcabbbbbbbbacccbabbcbaacccccacaaacac...

output:

result:

ok single line: '1461098'

Test #70:

score: 0

Accepted

time: 171ms

memory: 114844kb

input:

bcacccccbaccacabaaccbcabaacaabacbbcbaabbbacbccccbaccbaccbcacbaababcabacabcbbaacbbbbbacacbcbabbbccaccaaabcbbabcababbbbaccbaabbbcabbbccaccacbcabcbacccbbaccaaccccbcaabcbbbbccccbcaabccbbaabbbacbcbacaacccbbaacaaccabcacbacccabbcbbcbaccacbcabaaccabbbcbaaabbcccccccccacbcabccababacbaaaacaacbbbbccbcbcabaaaaab...

output:

result:

ok single line: '1686851'

Test #71:

score: 0

Accepted

time: 159ms

memory: 115256kb

input:

ccacaabaccaccbbbaaccccbacbbaabcbbbbbaaaccaacccabacaabbcaabbcbbcaaacbcabbbbcaabaabcaacacbaacbbbcaaaacbccccacbbbbbcbacbabcabaabbabcbcccaaacbccccababbaaacacbbbccccaaaabcccbcbcbcbbcabccccbcaaacccaaaaacbcbcbbaccbccbccbabcbcbacbabaccbcabababbbccbbababbbccabbbbcbacacaaabcbabacbacacccbabccccbaccaaaabccbcaca...

output:

result:

ok single line: '1610700'

Test #72:

score: 0

Accepted

time: 153ms

memory: 112840kb

input:

cbccacbbcbaccababaaabbcbbabaabbcbcabaacbaccbcabccbcbcacabacaaaaaacbaccabccaccccbcaacabaccaaacbabcbbbaabacacabcbcaaabbbcabaccacbbacaabbcacbabbbbbccbccccbbbbbcacaabcacccccabcbbcbbacbabbcaaacacabbbaaaaabababbbcccccbacbabaaaaabaaacabababcacbcccbacccccbbcbcbbacbbccbaaabbccabcbaabcabaabcbcaccbcbbbcabccbbc...

output:

367106043

result:

ok single line: '367106043'

Test #73:

score: 0

Accepted

time: 135ms

memory: 110992kb

input:

cccaaababbaabbcbcccccaaaacabbaabbabbccbcbccbbbcccbcbbaababbaabacacccaaaccbacabbccababcabcbacaaabbbaabbaccccbbcbbbaccacaaccacbcbbabacaacabccaaccacaacabaaaabbbbcbcbbcbccbabcbcaacbcbaacbcbaabbbbaaabacbbbbccbccacacaaacccccbbababccaaaccbabbaababbbbccccaacacacbacbcbabbaacbbcaccacacbbabacbcacbacbbaacbabcca...

output:

1670407588

result:

ok single line: '1670407588'

Test #74:

score: 0

Accepted

time: 141ms

memory: 107716kb

input:

bbbbbccbccccccbbccbbcaccaacaaaaccccaccaabbbaabbbabaabbaaabaabbbaaaabaaabababaabbaabbbbaabaabbbbaabbbbbaaababbaaabbaaaaaabbbabababbabbbabbabaabbabaaaabababaaabbbabbbbbaababaaaababbabbbabaaababbbabaaaaaaabbbbabbbaaabbccccccbbbccbbccbcbccbbcbcbbbcbcbcbcbccccbcbcbccccbbbccbbbcbbbbcbcbbcbcbccbcccccbccbcc...

output:

result:

ok single line: '6885652'

Test #75:

score: 0

Accepted

time: 24ms

memory: 98024kb

input:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

45000150000

result:

ok single line: '45000150000'

Test #76:

score: 0

Accepted

time: 164ms

memory: 116768kb

input:

abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc...

output:

14997350223

result:

ok single line: '14997350223'

Test #77:

score: 0

Accepted

time: 128ms

memory: 113524kb

input:

cbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcb...

output:

15000350001

result:

ok single line: '15000350001'