#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
int converted[100005];
int idx = 0;
long double fromleft[16][16][100005];
long double fromright[16][16][100005];
vector<vector<int>> groups;
int g;
long double calc(int amt) {
return (long double) ((long double) amt * (long double) (amt-1.0)) / 4.0;
}
long double getans(int mask, int j, int k) {
if (k >= groups[j].size()) return 1e15;
long double val = calc(k + 1) + calc((int) groups[j].size() - k - 1);
for (int i = 0; i < g; i++) {
if ((1 << i) & mask) {
val += fromleft[j][i][groups[j][k]];
if (k + 1 == groups[j].size()) continue;
val += fromright[j][i][groups[j][k+1]];
}
}
return val;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
string s; cin >> s;
int n = s.size();
set<char> dup;
map<char, int> m;
for (int i = 0; i < n; i++) {
if (m.find(s[i]) != m.end()) {
converted[i] = m[s[i]];
} else {
m[s[i]] = idx++;
converted[i] = m[s[i]];
}
}
g = idx;
groups.resize(g+1);
for (int i = 0; i < n; i++) {
groups[converted[i]].push_back(i);
}
for (int l = 0; l < g; l++) {
for (int r = 0; r < g; r++) {
long double ct = 0, res = 0;
for (int i = 0; i < n; i++) {
if (converted[i] == l) {
ct++;
} else if (converted[i] == r) {
res += ct;
fromleft[r][l][i] = res;
}
}
ct = 0, res = 0;
for (int i = n - 1; ~i; i--) {
if (converted[i] == l) {
ct++;
} else if (converted[i] == r) {
res += ct;
fromright[r][l][i] = res;
}
}
}
}
vector<long double> dp(1 << g, 1e15);
dp[0] = 0;
for (int mask = 0; mask < (1 << g); mask++) {
for (int j = 0; j < g; j++) {
if (!((1 << j) & mask)) {
long double cur = calc(groups[j].size());
for (int i = 0; i < g; i++) {
if ((1 << i) & mask) {
cur += fromleft[j][i][groups[j].back()];
}
}
for (int k = 0; k < groups[j].size(); k++) {
// up to k from front
cur = min(cur, getans(mask, j, k));
}
dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + cur);
}
}
}
cout << setprecision(30) << fixed << dp[(1 << g) - 1];
}
Compilation message
passes.cpp: In function 'long double getans(int, int, int)':
passes.cpp:45:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | if (k >= groups[j].size()) return 1e15;
| ~~^~~~~~~~~~~~~~~~~~~
passes.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if (k + 1 == groups[j].size()) continue;
| ~~~~~~^~~~~~~~~~~~~~~~~~~
passes.cpp: In function 'int main()':
passes.cpp:132:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (int k = 0; k < groups[j].size(); k++) {
| ~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 |
Correct |
0 ms |
212 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 |
Correct |
0 ms |
212 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 |
Correct |
0 ms |
212 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 |
Correct |
0 ms |
212 KB |
found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 |
Correct |
4 ms |
1428 KB |
found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 |
Correct |
4 ms |
1552 KB |
found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 |
Correct |
4 ms |
1556 KB |
found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 |
Correct |
4 ms |
1556 KB |
found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 |
Correct |
0 ms |
212 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 |
Correct |
1 ms |
980 KB |
found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 |
Correct |
1 ms |
980 KB |
found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 |
Correct |
1 ms |
980 KB |
found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 |
Correct |
1 ms |
852 KB |
found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 |
Correct |
1 ms |
980 KB |
found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 |
Incorrect |
1 ms |
724 KB |
1st numbers differ - expected: '55.5000000000', found: '59.0000000000', error = '0.0630630631' |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 |
Correct |
0 ms |
212 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 |
Correct |
1 ms |
980 KB |
found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 |
Correct |
1 ms |
980 KB |
found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 |
Correct |
1 ms |
980 KB |
found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 |
Correct |
1 ms |
852 KB |
found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 |
Correct |
1 ms |
980 KB |
found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 |
Incorrect |
1 ms |
724 KB |
1st numbers differ - expected: '55.5000000000', found: '59.0000000000', error = '0.0630630631' |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 |
Correct |
0 ms |
212 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 |
Correct |
0 ms |
212 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 |
Correct |
0 ms |
212 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 |
Correct |
0 ms |
212 KB |
found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 |
Correct |
4 ms |
1428 KB |
found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 |
Correct |
4 ms |
1552 KB |
found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 |
Correct |
4 ms |
1556 KB |
found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 |
Correct |
4 ms |
1556 KB |
found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
10 |
Correct |
0 ms |
340 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
11 |
Correct |
0 ms |
212 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
12 |
Correct |
1 ms |
980 KB |
found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
13 |
Correct |
1 ms |
980 KB |
found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
14 |
Correct |
1 ms |
980 KB |
found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
15 |
Correct |
1 ms |
852 KB |
found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
16 |
Correct |
1 ms |
980 KB |
found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
17 |
Incorrect |
1 ms |
724 KB |
1st numbers differ - expected: '55.5000000000', found: '59.0000000000', error = '0.0630630631' |
18 |
Halted |
0 ms |
0 KB |
- |