Advertisement
Guest User

Untitled

a guest
Dec 6th, 2019
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. ios::sync_with_stdio(0);
  6. int t;
  7. cin >> t;
  8. for (int test_case = 0; test_case < t; test_case++) {
  9. string s;
  10. cin >> s;
  11. int b = 0;
  12. int g = 0;
  13. for (auto c : s) {
  14. if (c == 'b') b++;
  15. else g++;
  16. }
  17. if (g > b) swap(b, g);
  18. int b_mid = g - 1;
  19. int b_left = (b - b_mid)/2;
  20. int b_right = b - b_mid - b_left;
  21. string t;
  22. for (int i = 0; i < b_left; i++) t += 'b';
  23. for (int i = 0; i < g; i++) {
  24. if (i) t += 'b';
  25. t += 'g';
  26. }
  27. for (int i = 0; i < b_right; i++) t += 'b';
  28. assert(t.size() == b + g);
  29. long long ans = 0;
  30. int b_count = 0;
  31. long long tmp = 0;
  32. for (int i = 0; i < t.size(); i++) {
  33. tmp += b_count;
  34. if (t[i] == 'b') b_count++;
  35. else ans += tmp;
  36. }
  37. b_count = 0;
  38. tmp = 0;
  39. for (int i = (int)t.size() - 1; i >= 0; i--) {
  40. tmp += b_count;
  41. if (t[i] == 'b') b_count++;
  42. else ans += tmp;
  43. }
  44. //cout << t << ": " << ans << endl;
  45. if (test_case) cout << " ";
  46. cout << ans;
  47. }
  48. cout << endl;
  49. return 0;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement