Submission #19540644


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;

template <class T> 
class FenwickTree {
    int N;
    vector<T> v;

    public:
    FenwickTree(int N) : N(N), v(N) {}

    void add(int p, T val) {
        for(int i = p; i < N; i += (i & -i)) {
            v[i] += val;
        }
    }

    T query(int p) {
        T sum = 0;
        for(int i = p; i >= 1; i -= (i & -i)) {
            sum += v[i];
        }
        return sum;
    }
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	string s;
	cin >> s;

	int n = s.size();

	vector<vector<int> > p(26);
	for (int i = 0; i < n; ++i) {
		p[s[i] - 'a'].emplace_back(i);
	}

	int cnt = 0;
	for (int i = 0; i < 26; ++i) {
		cnt += (int)p[i].size() & 1;
	}

	if (cnt > (n & 1)) {
		cout << -1 << '\n';
		exit(0);
	}

	vector<pair<int, int> > seg;
	for (int i = 0; i < 26; ++i) {
		int m = p[i].size();
		for (int j = 0; j < m && m - j - 1 >= j; ++j) {
			seg.emplace_back(p[i][j], p[i][m - j - 1]);	
		}
	}

	FenwickTree<int> fw(n + 1);
	long long ans = 0;
	for (auto [x, y] : seg) {
		fw.add(y + 1, 1);	
	}

	for (auto [x, y] : seg) {
		if (x == y) {
			ans += fw.query(x); 
		} else {
			ans += fw.query(x) * 2;
		}
	}

	for (auto [x, y] : seg) {
		fw.add(y + 1, -1);
	}

	sort(seg.begin(), seg.end(), [&] (auto x, auto y) {
		return x.second < y.second;
	});

	for (auto [x, y] : seg) {
		ans += fw.query(y) - fw.query(x);
		fw.add(y + 1, 1);
		fw.add(x + 1, -1);
	}

	cout << ans << '\n';

	return 0;
}

Submission Info

Submission Time
Task E - Papple Sort
User I9992147
Language C++ (GCC 9.2.1)
Score 0
Code Size 1564 Byte
Status WA
Exec Time 37 ms
Memory 6256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 3
AC × 42
WA × 8
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt WA 31 ms 5948 KB
02.txt AC 25 ms 6012 KB
03.txt WA 29 ms 5980 KB
04.txt AC 23 ms 5976 KB
05.txt WA 22 ms 5908 KB
06.txt AC 24 ms 6160 KB
07.txt WA 26 ms 6020 KB
08.txt AC 25 ms 6012 KB
09.txt WA 28 ms 6076 KB
10.txt AC 22 ms 6116 KB
11.txt AC 5 ms 4628 KB
12.txt AC 5 ms 4664 KB
13.txt AC 8 ms 4644 KB
14.txt AC 6 ms 4620 KB
15.txt AC 21 ms 5844 KB
16.txt AC 21 ms 5812 KB
17.txt AC 23 ms 5800 KB
18.txt AC 27 ms 5868 KB
19.txt AC 25 ms 5960 KB
20.txt AC 6 ms 4720 KB
21.txt AC 28 ms 5812 KB
22.txt AC 29 ms 5856 KB
23.txt AC 27 ms 5792 KB
24.txt AC 11 ms 4596 KB
25.txt AC 37 ms 5804 KB
26.txt AC 28 ms 5864 KB
27.txt AC 29 ms 5952 KB
28.txt AC 24 ms 5872 KB
29.txt AC 23 ms 5892 KB
30.txt AC 5 ms 4712 KB
31.txt AC 28 ms 5924 KB
32.txt AC 6 ms 4608 KB
33.txt WA 28 ms 6256 KB
34.txt AC 7 ms 4652 KB
35.txt WA 26 ms 6180 KB
36.txt AC 6 ms 4756 KB
37.txt AC 6 ms 4616 KB
38.txt AC 5 ms 4748 KB
39.txt WA 32 ms 6236 KB
40.txt AC 8 ms 4692 KB
41.txt AC 2 ms 3428 KB
42.txt AC 2 ms 3484 KB
43.txt AC 3 ms 3448 KB
44.txt AC 3 ms 3492 KB
45.txt AC 2 ms 3492 KB
46.txt AC 2 ms 3452 KB
47.txt AC 2 ms 3508 KB
s1.txt AC 3 ms 3528 KB
s2.txt AC 1 ms 3452 KB
s3.txt AC 2 ms 3448 KB