Submission #8895553
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define int long long // #define double long double #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define FORR(i, a, b) for(int i = (a); i > (b); --i) #define REP(i, n) for(int i = 0; i < (n); ++i) #define REPR(i, n) for(int i = n; i >= 0; i--) #define FOREACH(x, a) for(auto &(x) : (a)) #define VECCIN(x) \ for(auto &youso_ : (x)) cin >> youso_ #define bitcnt(x) __builtin_popcount(x) #define lbit(x) __builtin_ffsll(x) #define rbit(x) __builtin_clzll(x) #define SZ(x) ((long long)(x).size()) #define fi first #define se second #define All(a) (a).begin(), (a).end() #define rAll(a) (a).rbegin(), (a).rend() #define cinfast() cin.tie(0), ios::sync_with_stdio(false) #define PERM(c) \ sort(All(c)); \ for(bool cp = true; cp; cp = next_permutation(All(c))) #define MKORDER(n) \ vector<int> od(n); \ iota(All(od), 0LL); template <typename T = long long> inline T IN() { T x; cin >> x; return (x); } inline void CIN() {} template <class Head, class... Tail> inline void CIN(Head &&head, Tail &&... tail) { cin >> head; CIN(move(tail)...); } #define CCIN(...) \ char __VA_ARGS__; \ CIN(__VA_ARGS__) #define DCIN(...) \ double __VA_ARGS__; \ CIN(__VA_ARGS__) #define LCIN(...) \ long long __VA_ARGS__; \ CIN(__VA_ARGS__) #define SCIN(...) \ string __VA_ARGS__; \ CIN(__VA_ARGS__) #define Yes(a) cout << (a ? "Yes" : "No") << "\n" #define YES(a) cout << (a ? "YES" : "NO") << "\n" #define Printv(v) \ { \ FOREACH(x, v) { cout << x << " "; } \ cout << "\n"; \ } template <typename T = string> inline void eputs(T s) { cout << s << "\n"; exit(0); } template <typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); } template <typename T> using PQG = priority_queue<T, vector<T>, greater<T>>; template <typename T> using PQ = priority_queue<T>; typedef long long ll; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<ll, ll> PL; typedef vector<PL> VPL; typedef vector<bool> VB; typedef vector<double> VD; typedef vector<string> VS; const int INF = 1e9; const int MOD = 1e9 + 7; // const int MOD = 998244353; const ll LINF = 1e18; const double PI = atan(1.0) * 4.0; const ll dw[] = {1, 1, 0, -1, -1, -1, 0, 1}; const ll dh[] = {0, 1, 1, 1, 0, -1, -1, -1}; #define PI 3.141592653589793238 // 0-indexed template <class T> struct BinaryIndexedTree { vector<T> data; BinaryIndexedTree(int sz) { data.assign(++sz, 0); } T sum(int k) { T ret = 0; for(++k; k > 0; k -= k & -k) ret += data[k]; return (ret); } void add(int k, T x) { for(++k; k < data.size(); k += k & -k) data[k] += x; } }; template <class T> struct AdditionalBIT : BinaryIndexedTree<T> { int curr; AdditionalBIT(int sz) : BinaryIndexedTree<T>(sz) { curr = 1; while(curr <= sz) curr <<= 1; } int lower_bound(T w) { if(w <= 0) return (0); int i = 0; for(int k = curr; k > 0; k >>= 1) { if(i + k < BinaryIndexedTree<T>::data.size() && BinaryIndexedTree<T>::data[i + k] < w) { w -= BinaryIndexedTree<T>::data[i + k]; i += k; } } return (i); } }; VL idxs[26]; signed main() { string S; cin >> S; ll N = S.length(); REP(i, N) { idxs[S[i] - 'a'].emplace_back(i); } ll ocnt = 0; char center = '#'; ll ccnt = 0; REP(i, 26) { if(idxs[i].size() % 2) { ocnt++; center = 'a' + i; ccnt = idxs[i].size(); } } if(ocnt > N % 2) eputs(-1); VD od(N, -1); ll num = 0; VL tmp(26); REP(i, N) { if(od[i] >= 0) continue; if(S[i] == center && tmp[S[i] - 'a'] == ccnt / 2) { od[i] = N / 2; } else { ll r = *idxs[S[i] - 'a'].rbegin(); idxs[S[i] - 'a'].pop_back(); od[i] = num; od[r] = N - 1 - num; num++; } tmp[S[i] - 'a']++; } AdditionalBIT<ll> bit(N + 1); ll ans = 0; REP(i, N) { ans += i - bit.sum(od[i]); bit.add(od[i], 1); } cout << ans << "\n"; }
Submission Info
Submission Time | |
---|---|
Task | E - Papple Sort |
User | arktan763 |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 5433 Byte |
Status | AC |
Exec Time | 17 ms |
Memory | 5624 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 800 | ||||
Status |
|
|
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 | AC | 16 ms | 5508 KB |
02.txt | AC | 16 ms | 5380 KB |
03.txt | AC | 16 ms | 5508 KB |
04.txt | AC | 16 ms | 5508 KB |
05.txt | AC | 16 ms | 5380 KB |
06.txt | AC | 16 ms | 5380 KB |
07.txt | AC | 16 ms | 5380 KB |
08.txt | AC | 16 ms | 5380 KB |
09.txt | AC | 16 ms | 5380 KB |
10.txt | AC | 16 ms | 5380 KB |
11.txt | AC | 9 ms | 2180 KB |
12.txt | AC | 9 ms | 2180 KB |
13.txt | AC | 9 ms | 2308 KB |
14.txt | AC | 9 ms | 2308 KB |
15.txt | AC | 16 ms | 5236 KB |
16.txt | AC | 16 ms | 5236 KB |
17.txt | AC | 17 ms | 5296 KB |
18.txt | AC | 16 ms | 5316 KB |
19.txt | AC | 17 ms | 5304 KB |
20.txt | AC | 9 ms | 2168 KB |
21.txt | AC | 17 ms | 5360 KB |
22.txt | AC | 16 ms | 5316 KB |
23.txt | AC | 15 ms | 5240 KB |
24.txt | AC | 9 ms | 2680 KB |
25.txt | AC | 16 ms | 5236 KB |
26.txt | AC | 16 ms | 5236 KB |
27.txt | AC | 15 ms | 5364 KB |
28.txt | AC | 15 ms | 5240 KB |
29.txt | AC | 16 ms | 5364 KB |
30.txt | AC | 9 ms | 2292 KB |
31.txt | AC | 16 ms | 5364 KB |
32.txt | AC | 9 ms | 2552 KB |
33.txt | AC | 15 ms | 5624 KB |
34.txt | AC | 9 ms | 2680 KB |
35.txt | AC | 15 ms | 5624 KB |
36.txt | AC | 9 ms | 3064 KB |
37.txt | AC | 9 ms | 2508 KB |
38.txt | AC | 9 ms | 2928 KB |
39.txt | AC | 17 ms | 5232 KB |
40.txt | AC | 9 ms | 2128 KB |
41.txt | AC | 1 ms | 256 KB |
42.txt | AC | 1 ms | 256 KB |
43.txt | AC | 1 ms | 256 KB |
44.txt | AC | 1 ms | 256 KB |
45.txt | AC | 1 ms | 256 KB |
46.txt | AC | 1 ms | 256 KB |
47.txt | AC | 1 ms | 256 KB |
s1.txt | AC | 1 ms | 256 KB |
s2.txt | AC | 1 ms | 256 KB |
s3.txt | AC | 1 ms | 256 KB |