Advertisement
bibaboba12345

Untitled

Jan 8th, 2023
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.23 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <bitset>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <random>
  7. #include <map>
  8. #include <set>
  9. #include <deque>
  10. #include <cassert>
  11. const int N = 2e5 + 7, A = 26, MOD = 1e9+7, C = 2;
  12. using namespace std;
  13.  
  14. int lb(int a) {
  15. return a & (-a);
  16. }
  17.  
  18. struct Fenwick {
  19. int f[N];
  20. void add(int i, int val) {
  21. for (i; i < N; i += lb(i)) {
  22. f[i] += val;
  23. }
  24. }
  25. int get(int i) {
  26. int ans = 0;
  27. for (i; i > 0; i -= lb(i)) {
  28. ans += f[i];
  29. }
  30. return ans;
  31. }
  32. };
  33. Fenwick F;
  34.  
  35. string s,order;
  36.  
  37. bool pos[N];
  38. int cnt[A],cnt2[A], nxt[N], cur[A], prv[A], n;
  39.  
  40.  
  41. signed main()
  42. {
  43. #ifdef _DEBUG
  44. freopen("input.txt", "r", stdin);
  45. #else
  46. std::ios::sync_with_stdio(false);
  47. cin.tie(0);
  48. #endif
  49. cin >> s;
  50. n = s.size();
  51. for (int i = 0; i < n; i++) {
  52. cnt[s[i] - 'a']++;
  53. F.add(i + 1, 1);
  54. }
  55. int cnt_nechet = 0;
  56. for (int i = 0; i < A; i++) {
  57. if (cnt[i] % 2) {
  58. cnt_nechet++;
  59. }
  60. }
  61. if (cnt_nechet > 1) {
  62. cout << -1;
  63. return 0;
  64. }
  65. for (int i = 0; i < n; i++) {
  66. cnt2[s[i] - 'a']++;
  67. if (cnt2[s[i] - 'a'] > cnt[s[i] - 'a'] / 2 + cnt[s[i] - 'a'] % 2) {
  68. pos[i] = 1;
  69. order.push_back(s[i]);
  70. }
  71. nxt[i] = -1;
  72. }
  73. reverse(order.begin(), order.end());
  74. if (cnt_nechet == 1) {
  75. for (int i = 0; i < A; i++) {
  76. if (cnt[i] & 1) {
  77. order.push_back(i + 'a');
  78. }
  79. }
  80. }
  81. for (int i = 0; i < A; i++) {
  82. cur[i] = -1;
  83. prv[i] = -1;
  84. }
  85. for (int i = 0; i < n; i++) {
  86. if (prv[s[i] - 'a'] == -1) {
  87. prv[s[i] - 'a'] = i;
  88. cur[s[i] - 'a'] = i;
  89. }
  90. else {
  91. nxt[prv[s[i] - 'a']] = i;
  92. prv[s[i] - 'a'] = i;
  93. }
  94. }
  95. long long ans = 0;
  96. for (int i = 0; i < order.size(); i++) {
  97. int c = order[i] - 'a';
  98. int ind = cur[c];
  99. int swap_num = F.get(ind);
  100. ans += swap_num;
  101. F.add(ind + 1, -1);
  102. cur[c] = nxt[ind];
  103. }
  104. cout << ans;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement