#include <bits/stdc++.h>
using namespace std;
#define int int64_t
vector<vector<int>> groups;
int n, g;
vector<vector<int>> groupPFS;
void generateGroupPFS() {
for (auto i: groups) {
vector<int> pfs = {0};
for (int j = 0; j<n; j++) {
pfs.push_back(pfs.back() + binary_search(i.begin(), i.end(), j));
}
groupPFS.push_back(pfs);
}
}
vector<vector<vector<int>>> prefixsum;
void init() {
generateGroupPFS();
prefixsum.assign(g, vector<vector<int>>(g));
for (int i = 0; i<g; i++) {
for (int j = 0; j<g; j++) {
// if (i == j) continue;
vector<pair<int, int>> costPerElem;
for (int k = 0; k<groups[i].size(); k++) {
int l = groupPFS[j][groups[i][k]] - groupPFS[j][0];
int r = groupPFS[j][n] - groupPFS[j][groups[i][k]];
costPerElem.push_back({l, r});
}
// for (auto i: costPerElem) {
// cerr << i.first << " ";
// }
// cerr << "\n";
// for (auto i: costPerElem) {
// cerr << i.second << " ";
// }
// cerr << "\n\n";
vector<pair<int, int>> pfs(groups[i].size()+1, {0, 0});
for (int k = 1; k<=groups[i].size(); k++) {
pfs[k].first = pfs[k-1].first + costPerElem[k-1].first;
}
reverse(pfs.begin(), pfs.end());
reverse(costPerElem.begin(), costPerElem.end());
for (int k = 1; k<=groups[i].size(); k++) {
pfs[k].second = pfs[k-1].second + costPerElem[k-1].second;
}
reverse(costPerElem.begin(), costPerElem.end());
reverse(pfs.begin(), pfs.end());
// for (auto i: pfs) {
// cerr << i.first << " ";
// }
// cerr << "\n";
// for (auto i: pfs) {
// cerr << i.second << " ";
// }
// cerr << "\n\n";
vector<int> costForSplit;
for (int k = 0; k<=groups[i].size(); k++) {
costForSplit.push_back(pfs[k].first + pfs[k].second);
}
prefixsum[i][j] = costForSplit;
}
}
// for (int i = 0; i<g; i++) {
// for (int j = 0; j<g; j++) {
// for (int k: prefixsum[i][j]) {
// cerr << k << " ";
// }
// cerr << "\n";
// }
// cerr << "\n";
// }
}
struct binarySearch {
int getCostOneToOne(int from, int to, int pos) {
return prefixsum[from][to][pos];
}
double getSelfintersections(int from, int pos) {
int n1 = pos;
int n2 = groups[from].size()-pos;
return ((n1-1)*n1 + (n2-1)*n2)/4.0;
}
double getTotalCost(int from, int bm, int pos) {
double res = getSelfintersections(from, pos);
for (int j = 0; j<g; j++) {
if ((1<<j) & bm) {
res += getCostOneToOne(from, j, pos);
}
}
return res;
}
bool check(int from, int bm, int pos) {
if (pos + 1 > groups[from].size()) return 0 || check(from, bm, pos-1);
return getTotalCost(from, bm, pos) < getTotalCost(from, bm, pos+1);
}
double bs(int from, int bm) {
int l = 0; int r = groups[from].size();
for (int i = l; i<=r; i++) {
// cerr << getTotalCost(from, bm, i) << " ";
}
while (l<r) {
int m = (l + r) / 2;
if (check(from, bm, m)) r = m;
else l = m+1;
}
// cerr << " --" << l << "-- ";
return getTotalCost(from, bm, l);
}
};
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
string s; cin >> s;
n = s.size();
vector<vector<int>> groupsAlph(26);
for (int i = 0; i<n; i++) {
groupsAlph[s[i]-'A'].push_back(i);
}
for (auto i: groupsAlph) {
if (i.size()) groups.push_back(i);
}
g = groups.size();
init();
vector<int> order(g);
iota(order.begin(), order.end(), 0);
vector<double> dp(1<<g, 1e18);
dp[0] = 0;
for (int i = 1; i<1<<g; i++) {
for (int j = 0; j<g; j++) {
double res = 0;
if (1<<j & i) {
binarySearch bs;
res += bs.bs(j, i^(1<<j)) + dp[i^(1<<j)];
}
dp[i] = min(dp[i], res);
}
}
cout << dp[(1<<g)-1] << "\n";
// double res = 1e18;
// do {
// // for (int i: order) cerr << i << " ";
// // cerr << "\n";
// double tmpres = 0;
// int bm = 0;
// for (int i: order) {
// binarySearch bs;
// tmpres += bs.bs(i, bm);
// // cerr << "\n";
// bm += 1<<i;
// }
// // cerr << "\n";
// // cerr << tmpres << "\n";
// res = min(tmpres, res);
// } while (next_permutation(order.begin(), order.end()));
// // cerr << "\n\n";
// cout << setprecision(100) << res << "\n";
return 0;
}
Compilation message
passes.cpp: In function 'void init()':
passes.cpp:40:30: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (int k = 0; k<groups[i].size(); k++) {
| ~^~~~~~~~~~~~~~~~~
passes.cpp:58:30: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int k = 1; k<=groups[i].size(); k++) {
| ~^~~~~~~~~~~~~~~~~~
passes.cpp:64:30: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int k = 1; k<=groups[i].size(); k++) {
| ~^~~~~~~~~~~~~~~~~~
passes.cpp:81:30: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int k = 0; k<=groups[i].size(); k++) {
| ~^~~~~~~~~~~~~~~~~~
passes.cpp: In member function 'bool binarySearch::check(int64_t, int64_t, int64_t)':
passes.cpp:127:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | if (pos + 1 > groups[from].size()) return 0 || check(from, bm, pos-1);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
