QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#109432 | #6505. CCPC String | wnmrmr# | TL | 2ms | 3488kb | C++23 | 979b | 2023-05-29 01:01:51 | 2023-05-29 01:01:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define pb push_back
void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
void solve() {
string s; cin >> s;
int n = s.size();
if(n < 4) {
cout << 0 << '\n';
return;
}
vector<int> l(n, -1), r(n, n);
for(int i=0;i<n;i++) {
if(s[i] == 'p') l[i] = i;
else if(i) l[i] = l[i-1];
}
for(int i=n-1;i>=0;i--) {
if(s[i] == 'p') r[i] = i;
else if(i != n-1) r[i] = r[i+1];
}
int ans = 0;
for(int i=1;i<n-1;i++) if(s[i] == 'p' || s[i] == '?') {
int x = (i-1) - l[i-1], y = r[i+1] - (i+1);
ans += min(x / 2, y);
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while(t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3488kb
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: -100
Time Limit Exceeded
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 ...