#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define MP make_pair
const int N = 100500;
long double exp_inv(int n){
return (long double) n * (n - 1) / 4.0;
}
vector<int> pos[140];
void solve(){
string s;
cin >> s;
int n = (int)s.size();
string alphabet;
for (int i = 0; i < n; i++){
if (pos[s[i]].empty()) alphabet += s[i];
pos[s[i]].push_back(i);
}
sort(all(alphabet));
int m1 = (n - 1) / 2;
int m2 = m1 + 1;
long double ans = 1e18;
do {
long double tot = 0;
vector<bool> used(n, false);
for (char c : alphabet){
ll sum_l = 0;
vector<int> diff;
int sz = (int) pos[c].size();
for (int i : pos[c]){
int l = 0, r = 0;
for (int j = 1; j <= i; j++) l += used[j];
for (int j = i; j <= n; j++) r += used[j];
sum_l += l;
diff.push_back(r - l);
}
sort(all(diff));
long double cur = 1e18;
for (int half = 0; half <= sz; half++){
if (half > 0) sum_l += diff[half - 1];
cur = min(cur, sum_l + exp_inv(half) + exp_inv(sz - half));
}
for (int i : pos[c]) used[i] = true;
tot += cur;
}
ans = min(ans, tot);
} while (next_permutation(all(alphabet)));
cout << ans << endl;
}
int main() {
ios_base::sync_with_stdio(false);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
solve();
return 0;
}
Compilation message
passes.cpp: In function 'void solve()':
passes.cpp:23:21: warning: array subscript has type 'char' [-Wchar-subscripts]
23 | if (pos[s[i]].empty()) alphabet += s[i];
| ^
passes.cpp:24:17: warning: array subscript has type 'char' [-Wchar-subscripts]
24 | pos[s[i]].push_back(i);
| ^
passes.cpp:42:32: warning: array subscript has type 'char' [-Wchar-subscripts]
42 | int sz = (int) pos[c].size();
| ^
passes.cpp:44:30: warning: array subscript has type 'char' [-Wchar-subscripts]
44 | for (int i : pos[c]){
| ^
passes.cpp:60:30: warning: array subscript has type 'char' [-Wchar-subscripts]
60 | for (int i : pos[c]) used[i] = true;
| ^
passes.cpp:30:9: warning: unused variable 'm2' [-Wunused-variable]
30 | int m2 = m1 + 1;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 |
Correct |
1 ms |
212 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 |
Incorrect |
70 ms |
312 KB |
1st numbers differ - expected: '1023.0000000000', found: '1002.0000000000', error = '0.0205278592' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 |
Correct |
1 ms |
212 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 |
Incorrect |
70 ms |
312 KB |
1st numbers differ - expected: '1023.0000000000', found: '1002.0000000000', error = '0.0205278592' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603' |
2 |
Halted |
0 ms |
0 KB |
- |