This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(51);
#define ll long long
#define pb push_back
#define ld long double
const int G = 15, N = 1e5 + 10;
const ld INF = 1e18;
ll L[G][G][N], R[G][G][N];
vector<int> pos[G];
int g;
//a * (a - 1) / 4
ld func(int a) {
return (ld)a * (a - 1) / 4;
}
ll take_val(int mask, int j, int ind, bool f) {
if (ind < 0 || ind >= pos[j].size()) return 0;
ll res = 0;
for (int i = 0; i < g; i++) {
if (mask & (1 << i)) {
if (!f) {
res += L[j][i][pos[j][ind]];
} else {
res += R[j][i][pos[j][ind]];
}
}
}
return res;
}
ld get_ans(int mask, int j, int ind) {
if (ind >= pos[j].size()) {
return INF;
}
ld val = func(ind + 1) + func((int)(pos[j].size()) - ind - 1) + take_val(mask, j, ind, 0) + take_val(mask, j, ind + 1, 1);
return val;
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LOCAL
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
int n = s.size();
vector<int> a(n);
map<char, int> mp;
for (int i = 0; i < s.size(); i++) {
if (mp.count(s[i]) == 0) {
mp[s[i]] = mp.size();
}
a[i] = mp[s[i]];
}
g = mp.size();
vector<ld> dp((1 << g), INF);
for (int i = 0; i < n; i++) {
pos[a[i]].pb(i);
}
for (int i = 0; i < g; i++) {
for (int l = 0; l < g; l++) {
ll cnt = 0, res = 0;
for (int j = 0; j < n; j++) {
if (i == a[j]) {
res += cnt;
L[i][l][j] = res;
} else if (l == a[j]){
cnt++;
}
}
cnt = 0, res = 0;
for (int j = n - 1; j >= 0; j--) {
if (i == a[j]) {
res += cnt;
R[i][l][j] = res;
} else if (l == a[j]){
cnt++;
}
}
}
}
dp[0] = 0;
for (int mask = 0; mask < (1 << g); mask++) {
for (int j = 0; j < g; j++) {
if (!(mask & (1 << j))) {
ld bst = func(pos[j].size()) + min(take_val(mask, j, (int)(pos[j].size()) - 1, 0), take_val(mask, j, 0, 1));
int l = 0, r = (int)(pos[j].size()) - 1;
while (r - l > 2) {
int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
if (get_ans(mask, j, m1) > get_ans(mask, j, m2)) {
l = m1;
} else {
r = m2;
}
}
bst = min({bst, get_ans(mask, j, l), get_ans(mask, j, l + 1), get_ans(mask, j, r)});
dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + bst);
}
}
}
cout << setprecision(30) << fixed << dp[(1 << g) - 1] << endl;
return 0;
}
Compilation message (stderr)
passes.cpp: In function 'long long int take_val(int, int, int, bool)':
passes.cpp:24:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | if (ind < 0 || ind >= pos[j].size()) return 0;
| ~~~~^~~~~~~~~~~~~~~~
passes.cpp: In function 'long double get_ans(int, int, int)':
passes.cpp:39:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | if (ind >= pos[j].size()) {
| ~~~~^~~~~~~~~~~~~~~~
passes.cpp: In function 'int main()':
passes.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |