QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#292426#5474. Incredibly Cute Penguin ChicksDAleksaAC ✓1027ms761732kbC++143.4kb2023-12-28 04:45:582023-12-28 04:45:59

Judging History

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

  • [2023-12-28 04:45:59]
  • 评测
  • 测评结果:AC
  • 用时:1027ms
  • 内存:761732kb
  • [2023-12-28 04:45:58]
  • 提交

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'