fork download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. int main() {
  7. 	cin.tie(0)->sync_with_stdio(0);
  8. 	int t; cin >> t;
  9. 	while (t--) {
  10. 		int n; cin >> n;
  11. 		string s; cin >> s;
  12.  
  13. 		int start = 0;
  14. 		while (start < n && s[start] == 'B') {
  15. 			start++;
  16. 		}
  17.  
  18. 		if (start == n) {
  19. 			cout << "0\n";
  20. 			continue;
  21. 		}
  22.  
  23. 		vector<string> a; // groups of PP, PB
  24. 		int groups = 0;
  25. 		string cur = "";
  26. 		int ans = 0;
  27. 		int pp_cnt = 0; // total
  28. 		vector<pair<int, int>> pb_prevs; // index, # of pps before
  29. 		set<int> deleted;
  30.  
  31. 		for (int i = start; i < n; i++) {
  32. 			char c = s[i];
  33. 			if (c == 'P') {
  34. 				cur += c;
  35. 				if (cur == "PP") {
  36. 					a.push_back(cur); // always PP
  37. 					groups++;
  38. 					cur = "";
  39. 					pp_cnt++;
  40. 				} 
  41. 			} else { // c == 'B'
  42. 				if (cur == "P") {
  43. 					cur += c;
  44. 					a.push_back(cur);
  45. 					groups++;
  46. 					cur = "";
  47. 					pb_prevs.push_back({a.size() - 1, pp_cnt});
  48. 				} else if (cur == "B") {
  49. 					ans += a.size() * 2;
  50. 					cur = "";
  51. 				} else { // empty
  52. 					if (pb_prevs.size() == 0) { // just move it down
  53. 						ans += pp_cnt;
  54. 					} else { // combine with some PB from before
  55. 						pair<int, int> entry = pb_prevs.back();
  56. 						deleted.insert(entry.first);
  57. 						//cout << "deleted: " << entry.first << '\n';
  58. 						pb_prevs.pop_back();
  59. 						//cout << "adding first: " << pp_cnt - entry.second << '\n';
  60. 						//cout << "adding second: " << (entry.second) * 2 + pb_prevs.size() + 1 << '\n';
  61. 						ans += (pp_cnt - entry.second); // hopping over PPs
  62. 						ans += (entry.second) * 2 + pb_prevs.size() + 1; // all PP, PBs before as well as leftover P
  63. 						cur = "P"; // leftover P propagated up
  64. 					}
  65. 				}
  66. 			}
  67. 		}
  68.  
  69. 		//cout << "ans: " << ans << '\n';
  70.  
  71. 		vector<string> b;
  72. 		for (int i = 0; i < a.size(); i++) {
  73. 			if (deleted.find(i) != deleted.end()) continue;
  74. 			b.push_back(a[i]);
  75. 		}
  76.  
  77. 		// leftover [PB], [PP] blocks
  78.  
  79. 		pp_cnt = 0;
  80. 		int pb_cnt = 0;
  81. 		for (string block : b) {
  82. 			//cout << "block: " << block << '\n';
  83. 			if (block == "PP") pp_cnt++;
  84. 			else {
  85. 				ans += pp_cnt;
  86. 				pb_cnt++;
  87. 			}
  88. 		}
  89.  
  90. 		//cout << "ans: " << ans << '\n';
  91.  
  92. 		// pb cnt??
  93. 		int p_cnt = 0;
  94. 		//cout << "pb_cnt: " << pb_cnt << '\n';
  95. 		while (pb_cnt > 1) {
  96. 			ans += 2 + p_cnt;
  97. 			p_cnt += 2;
  98. 			pb_cnt -= 2;
  99. 		}
  100. 		if (pb_cnt == 1) {
  101. 			ans += p_cnt / 2 + 1;
  102. 		}
  103. 		cout << ans << '\n';
  104. 	}
  105. }
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5
3
PPP
3
BPP
3
PPB
7
PPBPPBB
15
BPBPBBBBBPBBBBB
stdout
copy 
0
0
1
5
14
https://ideone.com/xpVAGE
language:
C++ (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!