QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#292426 | #5474. Incredibly Cute Penguin Chicks | DAleksa | AC ✓ | 1027ms | 761732kb | C++14 | 3.4kb | 2023-12-28 04:45:58 | 2023-12-28 04:45:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int add(int x, int y) {
x += y;
if(x >= mod) x -= mod;
return x;
}
int sub(int x, int y) {
x -= y;
if(x < 0) x += mod;
return x;
}
int mul(int x, int y) {
return (x * 1LL * y) % mod;
}
void sadd(int& x, int y) {
x = add(x, y);
}
void ssub(int& x, int y) {
x = sub(x, y);
}
void smul(int& x, int y) {
x = mul(x, y);
}
struct Fenwick {
int n;
vector<int> fenw;
Fenwick() {
n = 0;
}
Fenwick(int _n) {
n = _n;
fenw.resize(n);
}
void update(int x, int val) {
for(int i = x; i < n; i += (i & -i)) {
sadd(fenw[i], val);
}
}
int get(int r) {
int ans = 0;
for(int i = r; i >= 1; i -= (i & -i)) {
sadd(ans, fenw[i]);
}
return ans;
}
int get(int l, int r) {
return sub(get(r), get(l - 1));
}
};
const int N = 1e6 + 10;
int dp[N][3];
int a[N], b[N], c[N];
Fenwick fw[3][2 * N];
vector<int> vals[3][2 * N];
int shift;
int get(int letter, int index, int x) {
index += shift;
x = upper_bound(vals[letter][index].begin(), vals[letter][index].end(), x) - vals[letter][index].begin();
return fw[letter][index].get(x, vals[letter][index].size());
}
void update(int letter, int index, int x, int val) {
index += shift;
x = lower_bound(vals[letter][index].begin(), vals[letter][index].end(), x) - vals[letter][index].begin();
fw[letter][index].update(x, val);
}
int solve(string s) {
int n = s.size();
shift = n;
s = "#" + s;
a[0] = b[0] = c[0] = 0;
for(int i = 1; i <= n; i++) {
a[i] = a[i - 1] + (s[i] == 'a');
b[i] = b[i - 1] + (s[i] == 'b');
c[i] = c[i - 1] + (s[i] == 'c');
}
for(int i = 0; i <= 2 * n; i++) {
for(int j = 0; j < 3; j++) {
vals[j][i].push_back(-1e9);
}
}
for(int i = 1; i <= n; i++) {
vals[0][b[i] - c[i] + shift].push_back(3 * b[i] - i);
vals[1][c[i] - a[i] + shift].push_back(3 * c[i] - i);
vals[2][a[i] - b[i] + shift].push_back(3 * a[i] - i);
}
for(int i = 0; i <= 2 * n; i++) {
for(int j = 0; j < 3; j++) {
sort(vals[j][i].begin(), vals[j][i].end());
fw[j][i] = Fenwick(vals[j][i].size() + 1);
}
}
for(int i = 1; i <= n; i++) {
sadd(dp[i][0], get(0, b[i] - c[i], 3 * b[i] - i));
sadd(dp[i][1], get(1, c[i] - a[i], 3 * c[i] - i));
sadd(dp[i][2], get(2, a[i] - b[i], 3 * a[i] - i));
if(a[i] == b[i] && c[i] > a[i]) sadd(dp[i][2], 1);
else if(a[i] == c[i] && b[i] > a[i]) sadd(dp[i][1], 1);
else if(b[i] == c[i] && a[i] > b[i]) sadd(dp[i][0], 1);
int tot = add(add(dp[i][0], dp[i][1]), dp[i][2]);
update(0, b[i] - c[i], 3 * b[i] - i, tot);
update(1, c[i] - a[i], 3 * c[i] - i, tot);
update(2, a[i] - b[i], 3 * a[i] - i, tot);
}
return add(add(dp[n][0], dp[n][1]), dp[n][2]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
string s;
cin >> s;
int n = s.size();
for(int i = 0; i < n; i++) {
if(s[i] == 'I') s[i] = 'a';
else if(s[i] == 'P') s[i] = 'b';
else s[i] = 'c';
}
cout << solve(s);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 39ms
memory: 336264kb
input:
ICPC
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 40ms
memory: 336992kb
input:
CCCIIIPPP
output:
69
result:
ok single line: '69'
Test #3:
score: 0
Accepted
time: 43ms
memory: 337208kb
input:
PICCICCIPPI
output:
24
result:
ok single line: '24'
Test #4:
score: 0
Accepted
time: 846ms
memory: 759668kb
input:
PCPPCCICPICPCPCPCCPPIPPPIICCCICPICCPPPIPCCCCICCIICPCCICCCPCICIPPIPIPIPPCCPCIPPCCPPCCIPPPIPPCIICIIIPPCIPPICPPICCPIICCCCCCCICPCCPPIPIPICPCIICPCCIPICCCPPCPIIICPCPPPIIIIICCCPCICCPPCPPCICIIIPIPICPCPPPPICPCPIPIIICCICPCIPPICCICPIIPPCCCIICPCPCCICCPICPPPPPPICCCIPCCICICIPICIIICCICPCIPIICPIPIIICCPCCIIPCCCCPIPI...
output:
216523282
result:
ok single line: '216523282'
Test #5:
score: 0
Accepted
time: 852ms
memory: 759836kb
input:
ICIPCICCIPIPIIPPCPCICICPCPCPIIICICPPICCICPIPCPCIIPPIPCCIPIPIPIICCICICCCIPPIIPCPPCIIICCICCCCCCPIPICCIPIICIICPIPCCICPPCCIPIPIICCCPCCIPCPPCCIIIIIPCIPIIPICIIIPIICCCIPPPIPICIIIICIIIPICIICPIPCCICIPCCIPICCCPPIPIIPICPPCPICIPIPPPPPCIPCCIPPICIPCICPCCCCPPIIIPCPICCICIPIIPICPIIIIPPPCPIIIPCCPPIIPPICPIIICCCPICPPIC...
output:
977504498
result:
ok single line: '977504498'
Test #6:
score: 0
Accepted
time: 834ms
memory: 760100kb
input:
PPCCCICCIPPICCPCCCCIPPPIICPIPIPPPPIPPPPPPCPIPICCPCCPICPIPPPIIPIPIIPPCCPIICPPIIIPPCCCIIPCCIPCCCCCCIIIPIPCICCIICIIICCCCPCCICPPCCPCCIPICCPPIIPIIPIPCIIPIIPPPCCIPCPCCICCIPICPPPCIPPIPCCPCPCCIPIICCIPCCIPPCPCIPICIICPPICIIICIPIIIIIPCCCPPIPPPCIICIIIPPCIPCIPCIICCCCPIPCPICICPIPCPPIPIPICCPCCCCPCIPCPPCCIPCCCCCPII...
output:
785880133
result:
ok single line: '785880133'
Test #7:
score: 0
Accepted
time: 867ms
memory: 759436kb
input:
ICIPCPIPCCCCCCCPCCPCCIPCPCPIPPCPIPCICPPIPPPPICPIIPPIICPICPICPPICICICCCIIPCPPCCICCCCPIICPPPIPIPCICPIPPPPCCPICPCPICICPPIIIICIICPPIPIIICCCCPIPIIPICCCIPCCPPCPPPPIIIIICIPCPCCPIIICICIPPCCPIPPCIIPCCCIIICPCIPCIIIIPCIIPCIICCCIPPIPPCIIPCICIPIIPICCICCPCPIICCCIPIICCCPIPPCCIIIICPPIICPCPCIPPPCPCICPPIPIPCCPIPPPIPI...
output:
687587235
result:
ok single line: '687587235'
Test #8:
score: 0
Accepted
time: 832ms
memory: 760188kb
input:
IICCCIPIIIIIPICIICPCPCIICCIIICCCIIPICICCCPCPCPPPIIPIPPICIICICIPIICCICCIIIPCIICCPPIPICIPPCPCPCPIICCIIICIPPICCICPPIPPPPICPCPIPCCCPCPCPPPPIICPCIIIIIIIPIPIICICCPPIIPPCICPCPCIPCPICPPPICCICIICPPIPPPIPIPIPPCIPPCIPPCPPPIICICCCPICIPPIPCCPIIPPCIPPICCIIIPPPPPIIPPICPCPCIPPCCPCIIIPPICCCIIIIICIPPIIICPCIIICPPCPCPP...
output:
698376687
result:
ok single line: '698376687'
Test #9:
score: 0
Accepted
time: 943ms
memory: 760348kb
input:
IIPICCCCIPPCCPICCIIPPPCIPCCPPIPIICICPCCIIPPCCCICICPPICCICPPIICIIPICPICIPPPPCPCCPIICCPPIPPCIIIIPICICICCIIPPCICCCCCPICPIPCPPCCPPICPICCCICCIPICCICPIICCPIPIPICCPPCCPCPCCPICCPICCCCCCIPIICPIPICICCPIIPIPICIICIPPPIPCICIPIPPICPICICPPICICCIPCIPPPCIPIIPPPIICICPPPIICCCPIIICIPIPPICICIPPPCCPCCIIPCCCPPPCPICPICPPCP...
output:
850857669
result:
ok single line: '850857669'
Test #10:
score: 0
Accepted
time: 619ms
memory: 739508kb
input:
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII...
output:
709758735
result:
ok single line: '709758735'
Test #11:
score: 0
Accepted
time: 630ms
memory: 739560kb
input:
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP...
output:
854001544
result:
ok single line: '854001544'
Test #12:
score: 0
Accepted
time: 616ms
memory: 739416kb
input:
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
output:
427000772
result:
ok single line: '427000772'
Test #13:
score: 0
Accepted
time: 826ms
memory: 757724kb
input:
IPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPC...
output:
717926203
result:
ok single line: '717926203'
Test #14:
score: 0
Accepted
time: 849ms
memory: 756692kb
input:
PCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCI...
output:
939976909
result:
ok single line: '939976909'
Test #15:
score: 0
Accepted
time: 824ms
memory: 757840kb
input:
CIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIPCIP...
output:
687951732
result:
ok single line: '687951732'
Test #16:
score: 0
Accepted
time: 741ms
memory: 741480kb
input:
IIIIIIIIICIIIIPIIIIIIIIPIIIPIIPIIIIIIIIIIIIPIIIIICIIIICIIIIIIIPCIIIIIIIIIPIIIIIIPIIIIICIIIIIIIIIIIIICIIIIIIICICIIIICIIIIIIPIIIIIIIIPIIIIIIICIIIIIPIIIIIIIIIIPCIPIICIPIIIICIIIIIIIIIIPICIIIIIPIIIIIIIIIIIIIIIPIIIIIIIIIIIIIIIIPIPPPCIPIIIICIIIIIIIIIIIIIIIIIIIICIIIIIIICIPIIIIPIIIIIIIIIIIIPIIIPICIIPIIIIIIII...
output:
955489074
result:
ok single line: '955489074'
Test #17:
score: 0
Accepted
time: 731ms
memory: 741544kb
input:
PPPPPPCPIPICPPPPPIPPPPPPPPPPCPPCPPPPPPPPPPPIPPPPPPPCPPPPPPPCIPICPIIPPPIPPPCCPPPPPPPPPPPPPPCPPPPPIPPCPPPPPPPPPPPPPPPCPPPPPPPIPPIPPPPPPPPPPPICIPPPPPPIIPCPPPCPPPCPPPPPPPPPPPPPICPPPPIPCPPPPPPCPIPPPPPPPPIPPPPPPPPPPPIIIPIPCPPPPPPPPPPPPPPIPPPPPPPPPPIPPPPCPPPPPPPPPPCPPIIPPPPPPPPPPPPPPPIPPPPPPPPPPPICPPPPPPPP...
output:
375091010
result:
ok single line: '375091010'
Test #18:
score: 0
Accepted
time: 656ms
memory: 741856kb
input:
CCCCCCCCCCCCCCCCPIPCCCCCCICCCCCCCCCCCCCICCCCCIPPCCCCCCCCCCICCCICCCCCCCCCCCCCCCCCPCCCCPCCPCCCCCCCCPCICCCCCPCICCPCCCCPCPCCCCCCCCCCCCICPCCPCPPCCCCCCCICICPCCCCCCCCCICICCCICCPPPPPCCCCPPCCICPCCCCCCCIICCPCICCCCCCCCICCCCCCCCICCICCCICCCCCCCCICCCCCCCCCCCCCCCCCIPCCCCCCCCCCICPCCCPICCCCPCCCCCCCCCCCCCCPCICICCICCC...
output:
270555678
result:
ok single line: '270555678'
Test #19:
score: 0
Accepted
time: 807ms
memory: 742100kb
input:
IIPIIIIIICIIPIICIIIIIIIIIIIIIPIIIPIIIIIIIIIIIIIIIIIIIIIIIIIIICIIIIIIPPIIIIIIPIIICCICIIPIICCIIPIIIPIIIIIIPIIIIIIIICIIIIIIIIIIICIIIPIIIIIICIICIIICIIIIPIICIIIPIIIIIIIPIIIIIPICIIIICICIIICIIIIIIIIIIIPICIIIIIIIIIIPPIIIICIIIIIIIIPIIIIIPIICIIIIIIICCIIPIIIICIIPIIIIIIIIIIIICIIIIIPIIPCIIIIIICICIIIIIIPIIIIIIIII...
output:
178987433
result:
ok single line: '178987433'
Test #20:
score: 0
Accepted
time: 711ms
memory: 741768kb
input:
PPPPPPPCIPPPPPPPCPPPPCIPPPCPPPPCPPIPPPPPPPPPPPPPCPPPPPPPPPPPIPPPPPIPPPIPPPPPPPPCCPPPPPPPPCPPPCPPPIPPPPPPPPIPPPPPPPPPPPPPPPPPPPPPPPIPPPPPPCPPIPPPPPPICPPPPPPPPCPPPPPPPPPPPPPPPCPPPPPPPCPPCPPPPPPPPPIPCPPCPPPPPPPCPIPPPPPIPPPPPPPPPPPPPCPPCIPPPCPPPPPPPPPPPPPPPPCPPPPPPPPPCPPPPPPIIPPPPPIPCPCIIPPPPPPPPPCPPPIP...
output:
328261068
result:
ok single line: '328261068'
Test #21:
score: 0
Accepted
time: 664ms
memory: 741716kb
input:
CCICCCCIPCCCCICCCCPCCCCCICCCCCCCCCCCCCCCICCCCPCCCCCCCCCCCCCCCICCCICCCCCCICCCCCCCCPCCCCCPPICCCCCCCICCCCCICCIIPPICCCICCCCCCCCCCICCCCCPCCCCICCCCCCICCIPCCPCIPCCCCPICPCCCCCICICCCCCCCCICPCCCPCCCPCCCPCCCCCCCCCPCPCCICPCCCCCICCPCCICCCPCCCCCCCCCCICCCCPCCCCCPCCCCCPCCCPCCCCCCCCCCCCCCCCCCCCPCICCCIICPCICPIICCCCCC...
output:
424185045
result:
ok single line: '424185045'
Test #22:
score: 0
Accepted
time: 747ms
memory: 741732kb
input:
IIIIIIIIIIPIIIIIIIIIIIIIIIIIICIIIIPPCIICICIPIIIIIPIIICPIIICIIPIPIIIIIIIIIIPIIIIIIIIPIPIIIPICIIIIIIPIIIIIPIIIIIIIIIIIIICIIIIPIIIIICIICICIIIIIIIIIIIIIIIIIIIIIIIIIICIPCIIIIIIPIIIIIIIIIIIIIICIIIIIIIIIIIIIIIIIIIIIIICIIIIIICIIIIIIIICCIIIIIIIIPIIIIIIIIPIIIPIIIIIICIIIIIIIIIIIIIICIIIICIIIIIIIIIPIIIIIIIIIIPII...
output:
595831650
result:
ok single line: '595831650'
Test #23:
score: 0
Accepted
time: 729ms
memory: 741572kb
input:
PCCPPPPCPPIPPPPCIPPPCIPCPPIPIPPPPPPIPPPIIPPPPCPPPPPPIPPPIPPPPCPPPIPPPPPPPPIPPPPIPCPPPPPPPPPIPPPPPPIIIPPPPPIPPCPPPPPIPPPPPPIPPPPPIPPPIPPPPPPCPPPPPPPPPPPPPCPPPPPPPPPPPPPPPPPIIPICPPCPPPPPCPPPPPPCPPPPPIPPPPPCCPPPPPPPIPPPPPPPPPIPPPPPICPPPPPIPPPPPIPCPPPPPPCPPPIPPPPPPPPPPCPPPPPPPPPIPPCPPPCCIIPPIIPPPPIPPPPP...
output:
354896912
result:
ok single line: '354896912'
Test #24:
score: 0
Accepted
time: 653ms
memory: 741636kb
input:
CPCCCCCCPPICICCPCCCCCCCCCPCCCCCCCCPPIPPCCCPCCCCCCPCICCCCCCCIPCCICICCCCCCCCCCCCCCCCCCIPCCCPCCCIPCPCCPCCPCCCCCPCCCCCCPCCCCICPCCCCCCCCCCCCCIICCCCCIPCIIICCCCCCCCPCCCCCCIICCCCCCCICPCCCCCCCCCCCICCCCIPCCCCCCCCCCPCCCICCCCPCCCCCCCCCCCCCCCPPCPCCCCICCCCCCCCCCCCCPCCCCICCCCCCCCCCIIICCCCCCCCCCCCCCCCICCCCCPCICIPIC...
output:
423510008
result:
ok single line: '423510008'
Test #25:
score: 0
Accepted
time: 789ms
memory: 744140kb
input:
IPCIIIIPCIIIIIICPIICPIIIIIIIICPIIIIPCICPPCPCIIIIIPCIIIIIICPIIIPCIIPCIIIIIICPIIIIIIIIIPCCPICPCPIIIIIIIIIIICPIPCIICPIIIIIIIIIIPCIIIICPIIIIIIIIIICPCPIIIIIIIIIIIIIIIIIPCIIIIIIPCIIIPCIIICPIIPCIIIPCCPPCIIIIIIIIIICPIIIIICPICPIIIIIIICPIICPIICPIIIIIIIIICPIIIIIIICPIICPIIIIIPCIIPCIIIIIIIIIIIPCIIIIIIIPCICPPCIII...
output:
803254087
result:
ok single line: '803254087'
Test #26:
score: 0
Accepted
time: 839ms
memory: 743716kb
input:
PPPPPPPPPPPPPPPPPPPPPPPICICPPPPPPPICPPPPCIPPPPPPICICPPPCIPPPPPCIPCIPPPCIPPICPPPPPPPCIPPPICPICPPPPPPPPPPPPPPPPPPPPICCIPPPCIPPPPPPPICCIPPPPPPPCIPPPCIPPPPPPPPPPPPICPPPPPPICPPPICPCIPPPPPPPPPPPPICCICIPPPPPPICPPPPPPPICCIPPCIPICPPPPCIPPCIPPPPPPPPPICCIPPPPPPPPPPPPCIPPPPPPPCIICPPPCIPPPCIPPCIPPICPPPPPCIPPPPCI...
output:
422010091
result:
ok single line: '422010091'
Test #27:
score: 0
Accepted
time: 763ms
memory: 743552kb
input:
CCPICCCCCCIPCCCCCCIPPICCCCPICCCCCCCCCCCCCCCCCCCCCIPPICCCCCCCCIPCCCCCCCCCPICCCCCCCPICCCCCCIPCIPCCCCCCCCCIPCCCCCCCCCCCPICCCCCCCCPICCIPCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCPICCPICCCPICCCPICCCCCCIPCIPCPICCCCCCCCIPCCCCCIPCCCCCCCCCCCCCPICCCCCCCCCCCCCIPCCCCCCPICCCCCCCCCCCCIPPICCCCPICCPICCCPICCCPICCPICIPCPICCCCCCC...
output:
81666193
result:
ok single line: '81666193'
Test #28:
score: 0
Accepted
time: 844ms
memory: 743512kb
input:
CPIIIIIICPIIIIICPPCIIPCCPIIIIIIICPPCIIIIIIIIIIIIIICPIIIIIIIIIIPCIIIIIIIIPCIIPCIPCIIPCIIIIIIIIIIICPIIICPPCIIIIIIIIIIIIICPIIIIIIIPCIIIIIIIIIIIIIIIIIIIIIIIIIPCIIIIIICPICPPCIIIIIIICPIIIPCICPIIIIICPCPICPIIIIIICPPCIIIIICPIIIIIIIICPIIPCIIIIIIIIIIIICPICPIIICPIIIIPCIICPIIPCIIPCIICPIIIIIIICPCPIIIIPCCPIIIIIPCC...
output:
739418046
result:
ok single line: '739418046'
Test #29:
score: 0
Accepted
time: 823ms
memory: 743964kb
input:
PCIPPPPPICPPPCIPPPPPCIPPPPPPPICPPPPPICPPPPPPPPCIICPPPPPICCIPPCIPPPPPPPICPPPPPPPPPPPPICCIPPPPPPCIPPPPPPPPPPPPPICPCIPPPPCIPPPICPICPPPPCIPPICPPPPPPPCIPPCIPCIPPPPPPPICPCIPICPPPICCIPPPPICPCIPPPPPPICPPPCIPPCIPPPPPPPPPPPPPPICICCIPPICPICPPPPCIPPPPICPPPPPPPPPPPPPPPPPPPPPPPICICPPPPPPPPPCIPCIPPPPPCIPPPCIICPICP...
output:
429005526
result:
ok single line: '429005526'
Test #30:
score: 0
Accepted
time: 739ms
memory: 743780kb
input:
PICIPCIPCCCCIPCCCIPCCIPCIPCCCCCCIPCCCCCCCCCCCCCCCCCIPPICCCCIPCCCCCCCCCIPCPICCCCCPICCCPIPICPICCCCCCIPCCPICIPCCIPCCCCCPICCCCCCCIPCCCIPCCCCCCPICCCCCCCPICCCCCCCCCCCIPCCCCCCCCCCCPICCCCCCCIPCIPCCPIPICCCIPCCCCCCCCCCCCCCCCCIPCCCCPICCIPCIPCCCCCCCIPCIPCCIPPICCCPICCPICCCCCCCPICCPICIPCCCCCPICCCCCPICCCCCCCPICCCC...
output:
346033550
result:
ok single line: '346033550'
Test #31:
score: 0
Accepted
time: 829ms
memory: 761732kb
input:
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII...
output:
876361609
result:
ok single line: '876361609'
Test #32:
score: 0
Accepted
time: 815ms
memory: 761204kb
input:
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP...
output:
51133400
result:
ok single line: '51133400'
Test #33:
score: 0
Accepted
time: 826ms
memory: 761068kb
input:
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
output:
881510334
result:
ok single line: '881510334'
Test #34:
score: 0
Accepted
time: 739ms
memory: 761304kb
input:
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII...
output:
703358165
result:
ok single line: '703358165'
Test #35:
score: 0
Accepted
time: 854ms
memory: 761180kb
input:
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP...
output:
8597778
result:
ok single line: '8597778'
Test #36:
score: 0
Accepted
time: 779ms
memory: 761544kb
input:
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
output:
875167427
result:
ok single line: '875167427'
Test #37:
score: 0
Accepted
time: 964ms
memory: 760944kb
input:
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII...
output:
339337501
result:
ok single line: '339337501'
Test #38:
score: 0
Accepted
time: 1027ms
memory: 761296kb
input:
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP...
output:
321201785
result:
ok single line: '321201785'
Test #39:
score: 0
Accepted
time: 975ms
memory: 760668kb
input:
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
output:
654943659
result:
ok single line: '654943659'
Test #40:
score: 0
Accepted
time: 621ms
memory: 739556kb
input:
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII...
output:
995448234
result:
ok single line: '995448234'
Test #41:
score: 0
Accepted
time: 596ms
memory: 739540kb
input:
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP...
output:
442950961
result:
ok single line: '442950961'
Test #42:
score: 0
Accepted
time: 659ms
memory: 739500kb
input:
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
output:
221475480
result:
ok single line: '221475480'
Test #43:
score: 0
Accepted
time: 752ms
memory: 748380kb
input:
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII...
output:
828731448
result:
ok single line: '828731448'
Test #44:
score: 0
Accepted
time: 737ms
memory: 747992kb
input:
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP...
output:
967126854
result:
ok single line: '967126854'
Test #45:
score: 0
Accepted
time: 727ms
memory: 747516kb
input:
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
output:
898792666
result:
ok single line: '898792666'
Test #46:
score: 0
Accepted
time: 53ms
memory: 336056kb
input:
I
output:
1
result:
ok single line: '1'
Test #47:
score: 0
Accepted
time: 55ms
memory: 337260kb
input:
P
output:
1
result:
ok single line: '1'
Test #48:
score: 0
Accepted
time: 35ms
memory: 336024kb
input:
C
output:
1
result:
ok single line: '1'
Test #49:
score: 0
Accepted
time: 44ms
memory: 335972kb
input:
IP
output:
1
result:
ok single line: '1'
Test #50:
score: 0
Accepted
time: 23ms
memory: 337044kb
input:
PP
output:
2
result:
ok single line: '2'
Test #51:
score: 0
Accepted
time: 37ms
memory: 336388kb
input:
CP
output:
1
result:
ok single line: '1'
Test #52:
score: 0
Accepted
time: 31ms
memory: 337512kb
input:
IP
output:
1
result:
ok single line: '1'
Test #53:
score: 0
Accepted
time: 50ms
memory: 337076kb
input:
PP
output:
2
result:
ok single line: '2'
Test #54:
score: 0
Accepted
time: 47ms
memory: 337380kb
input:
CP
output:
1
result:
ok single line: '1'
Test #55:
score: 0
Accepted
time: 32ms
memory: 336876kb
input:
IP
output:
1
result:
ok single line: '1'
Test #56:
score: 0
Accepted
time: 39ms
memory: 336896kb
input:
PP
output:
2
result:
ok single line: '2'
Test #57:
score: 0
Accepted
time: 44ms
memory: 335892kb
input:
CC
output:
2
result:
ok single line: '2'
Test #58:
score: 0
Accepted
time: 854ms
memory: 752436kb
input:
CICCCPPIICCCIPPPCPCCCPPICCIPPIPPCICPCCPPCCICPPPPPIIPPPCIPPPCCPPCPPPIPCPICPPPCPPPPPCIPIPCPPCCCCCCICPICPCPPPICIPPCPCPIPCCPPCPCPPCCCCIPPIICPPIICPPCPPIIPCICPPPCIICPCCCCPPPCCCCICCICIPCIPCPPPPCCCIPCCICPCCCCPCPICCCCCCPCPCPPCCPCPCPCCPIPPICPPIPPCCCPPICCCPPPPPCCPCICCPPCCCIIPPPIICCPCCPPCCIPCCCICCPPPICPCCPPICIC...
output:
382266009
result:
ok single line: '382266009'
Test #59:
score: 0
Accepted
time: 741ms
memory: 752260kb
input:
PICCPIIICICPICIIIPICPICCIPPIPPPCCCIIPIIPCIPCCIIIICPIIPPIPICCPIPCPIPPPPPICIICIICIICICICIPCIIICCIPCICIPCICPICCPCCICICCCIICPIPICPPPPICIPCCIIIIIIPCCICIIPCPICCCCPCICPIIIIPCCCCPICICCCICIPIIICICPIPCIPPIIPCIPIICICPICCIICICCCPCPCICCPICICIIICCCIPICCIIPIIPIICCICIPIPCCCCCIICPIIICIPIICICPIICICIPPPCIIICCCCPICICCC...
output:
510412653
result:
ok single line: '510412653'
Test #60:
score: 0
Accepted
time: 827ms
memory: 752348kb
input:
ICPCCIPPIPCIPCICPCCCIPCPPPPPPICPCPIPIIIPPCIIPIIPIPCCIIIIIIIIPICIIIPIPIIICIPICIIIIIICIIPICCCPIPIPCCPPCCPIPCICCIIPCPPIIIPPIICPIPIPPPPCIPIPIIPIIIICCPICIPCPCPCPPCICIPPICIIIPPPPPPCCIPIPICPCCICCCPICIPPIPPIPPPICPIPPCPCIIIPIPCPIICIIPIIIPCPPPICPICPIPIIIIIIICICIIPIIIPPIPIPICPPIIIIPCICICICCIIPPIIPIPCCCIPIPCCII...
output:
130104659
result:
ok single line: '130104659'
Test #61:
score: 0
Accepted
time: 865ms
memory: 746684kb
input:
CPIPCCPPCPCCPCPIIPCCPPCPCCPPCPCCPCPPCCPCPPCCPPCCPPCPCICPPCPCCPCPCPPCPCIIPCCPCPCPCPPCICPPCPCPCIPCPCPCCPPCCPCPCPPCCPIPCICPPCCPPCCPIPCPCPCCPPCPCCPIIPCICPPCCPPCIPCPCICPPCPCPCIICPPCPCPCPCCPCPPCPCPCICPIIPCIPCPCCPCPPCCPICPICPPCCPCPIPCICPCPPCPCICPPCCPCPCPCPPCCPPCCPPCPCPCCPCPCPICPPCPCCPICPPCPCCPCPCPIPCPCPCCP...
output:
892362548
result:
ok single line: '892362548'
Test #62:
score: 0
Accepted
time: 818ms
memory: 746300kb
input:
CIICPPICICPICCIICPICCIPCICICIPICICICPCIPCICICICICIICPICICICICICCICIICCICICIICICICCIPCIPCIPCIICCIPPICPICPCICIICPICCIICCIICCICIICCIICICCIPCICICIICCIICCICIICCICICIICPPICCIICICCIICPCIPCIICCICICIICICICICICCIPICICCIPPCIICCIICPCIICICCICIICCIICICICICICPICICICICICICCICIPCICICICIPCIICICCICICICIICICPCICICIICCI...
output:
249936867
result:
ok single line: '249936867'
Test #63:
score: 0
Accepted
time: 782ms
memory: 745372kb
input:
PIIPCIPCPIPICIPIPPIIPIPIPIPPICCIPIPPIIPIPPICCIPCIPPIIPCIPIPPIPIPIIPPIIPPIPICIPPIPIPIPICIPCIPIPPIPIIPIPPIPIIPPIPIPIIPPIIPPIPIPIPIIPCPIIPPICIPIPIPCIPCIPPIPIPICCPIPICIPIPPIPICCIPPIIPPIPICCIPPIPIPIIPIPIPCIPPIIPPIPICPICCPIPIIPPIPIIPCIPPIIPPIIPIPIPIPIPPICCCCIPIPIPIPCPIIPCIPPIIPCIPPICIPCIPCPIPIPIIPCIPPIPIP...
output:
278587043
result:
ok single line: '278587043'