QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#109432#6505. CCPC Stringwnmrmr#TL 2ms3488kbC++23979b2023-05-29 01:01:512023-05-29 01:01:52

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-29 01:01:52]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3488kb
  • [2023-05-29 01:01:51]
  • 提交

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();
}

详细

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
...

result: