Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <bitset>
- #include <vector>
- #include <algorithm>
- #include <random>
- #include <map>
- #include <set>
- #include <deque>
- #include <cassert>
- const int N = 2e5 + 7, A = 26, MOD = 1e9+7, C = 2;
- using namespace std;
- int lb(int a) {
- return a & (-a);
- }
- struct Fenwick {
- int f[N];
- void add(int i, int val) {
- for (i; i < N; i += lb(i)) {
- f[i] += val;
- }
- }
- int get(int i) {
- int ans = 0;
- for (i; i > 0; i -= lb(i)) {
- ans += f[i];
- }
- return ans;
- }
- };
- Fenwick F;
- string s,order;
- bool pos[N];
- int cnt[A],cnt2[A], nxt[N], cur[A], prv[A], n;
- signed main()
- {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- #else
- std::ios::sync_with_stdio(false);
- cin.tie(0);
- #endif
- cin >> s;
- n = s.size();
- for (int i = 0; i < n; i++) {
- cnt[s[i] - 'a']++;
- F.add(i + 1, 1);
- }
- int cnt_nechet = 0;
- for (int i = 0; i < A; i++) {
- if (cnt[i] % 2) {
- cnt_nechet++;
- }
- }
- if (cnt_nechet > 1) {
- cout << -1;
- return 0;
- }
- for (int i = 0; i < n; i++) {
- cnt2[s[i] - 'a']++;
- if (cnt2[s[i] - 'a'] > cnt[s[i] - 'a'] / 2 + cnt[s[i] - 'a'] % 2) {
- pos[i] = 1;
- order.push_back(s[i]);
- }
- nxt[i] = -1;
- }
- reverse(order.begin(), order.end());
- if (cnt_nechet == 1) {
- for (int i = 0; i < A; i++) {
- if (cnt[i] & 1) {
- order.push_back(i + 'a');
- }
- }
- }
- for (int i = 0; i < A; i++) {
- cur[i] = -1;
- prv[i] = -1;
- }
- for (int i = 0; i < n; i++) {
- if (prv[s[i] - 'a'] == -1) {
- prv[s[i] - 'a'] = i;
- cur[s[i] - 'a'] = i;
- }
- else {
- nxt[prv[s[i] - 'a']] = i;
- prv[s[i] - 'a'] = i;
- }
- }
- long long ans = 0;
- for (int i = 0; i < order.size(); i++) {
- int c = order[i] - 'a';
- int ind = cur[c];
- int swap_num = F.get(ind);
- ans += swap_num;
- F.add(ind + 1, -1);
- cur[c] = nxt[ind];
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement