#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn1 = 1e5+10;
const int maxn = 1e4+10;
const int maxg = 11;
int n, a[maxn1];
dbl pf[(1<<maxg)][maxn], dp[(1<<maxg)], prepl[maxg][maxg][maxn], prepr[maxg][maxg][maxn];
vector<int> pos[maxg];
void solve() {
string s; cin >> s;
n = s.size();
vector<char> cc;
for(auto x : s) cc.pb(x);
sort(all(cc));
cc.erase(unique(all(cc)),cc.end());
for(int i = 1; i <= n; i++) {
a[i] = lower_bound(all(cc),s[i-1])-cc.begin();
pos[a[i]].pb(i);
}
int g = cc.size();
if(g == 1) {
dbl ans = 0;
for(int i = 1; i <= n; i++) ans+= min((dbl) (i-1)/2,(dbl) (n-i)/2);
cout.setf(ios::fixed);
cout.precision(10);
cout << ans << endl;
return;
}
for(int mask = 1; mask < (1<<g); mask++) {
pf[mask][0] = 0;
for(int i = 1; i <= n; i++) {
pf[mask][i] = pf[mask][i-1];
if((1<<a[i])&mask) pf[mask][i]++;
}
}
for(int i = 0; i < g; i++) {
for(int j = 0; j < g; j++) {
for(int x = 1; x <= n; x++) {
prepl[i][j][x] = prepl[i][j][x-1];
if(pf[(1<<j)][x]-pf[(1<<j)][x-1]) prepl[i][j][x]+= pf[(1<<i)][x];
if(pf[(1<<i)][x]-pf[(1<<i)][x-1]) prepl[i][j][x]+= ((dbl) pf[(1<<i)][x-1])/2;
}
}
}
for(int i = 0; i < g; i++) {
for(int j = 0; j < g; j++) {
for(int x = n; x >= 0; x--) {
prepr[i][j][x] = prepr[i][j][x+1];
if(pf[(1<<j)][x]-pf[(1<<j)][x-1]) prepr[i][j][x]+= pf[(1<<i)][n]-pf[(1<<i)][x];
if(pf[(1<<i)][x]-pf[(1<<i)][x-1]) prepr[i][j][x]+= ((dbl) pf[(1<<i)][n]-pf[(1<<i)][x])/2;
}
}
}
for(int mask = 1; mask < (1<<g); mask++) {
dp[mask] = inf;
for(int i = 0; i < g; i++) {
if(((1<<i)&mask) == 0) continue;
int mask1 = mask-(1<<i);
int l = 1;
int r = pos[i].size();
int ans = 0;
// I want to find the greatest i such that I going to
// the left if better than i going to the right
while(l <= r) {
int mid = (l+r)/2;
int x = pos[i][mid-1];
// dbl ansl = pf[mask1][x]+((dbl) j-1)/2;
dbl ansl = ((dbl) mid-1)/2;
for(int j = 0; j < g; j++) {
if(((1<<j)&mask1) == 0) continue;
ansl+= pf[(1<<j)][x];
}
// dbl ansr = pf[mask1][n]-pf[mask1][x]+((dbl) sz-j)/2;
dbl ansr = ((dbl) pos[i].size()-mid)/2;
for(int j = 0; j < g; j++) {
if(((1<<j)&mask1) == 0) continue;
ansr+= pf[(1<<j)][n]-pf[(1<<j)][x];
}
if(ansl <= ansr) {
ans = mid;
l = mid+1;
}
else {
r = mid-1;
}
}
dbl ans1 = dp[mask1];
// for(int j = 0; j < g; j++) {
// if(((1<<j)&mask1) == 0) continue;
// ans1+= prepc[i][j][x];
// }
int sz = pos[i].size();
// for(int j = 1; j <= ans; j++) {
// int x = pos[i][j-1];
// ans1+= pf[mask1][x]+((dbl) j-1)/2;
// // cout << " " << min(pf[mask1][x]+((dbl) j-1)/2, pf[mask1][n]-pf[mask1][x]+((dbl) pos[i].size()-j)/2) << endl;
// }
if(ans != 0) {
for(int j = 0; j < g; j++) {
if(((1<<j)&mask1) == 0) continue;
ans1+= prepl[i][j][pos[i][ans-1]];
}
}
// if(ans != pos[i].size()) {
// for(int j = 0; j < g; j++) {
// if(((1<<j)&mask1) == 0) continue;
// ans1+= prepr[i][j][pos[i][ans-1]+1];
// }
// }
for(int j = ans+1; j <= pos[i].size(); j++) {
int x = pos[i][j-1];
ans1+= pf[mask1][n]-pf[mask1][x]+((dbl) sz-j)/2;
// cout << " " << min(pf[mask1][x]+((dbl) j-1)/2, pf[mask1][n]-pf[mask1][x]+((dbl) pos[i].size()-j)/2) << endl;
}
dp[mask] = min(dp[mask],ans1);
}
// dp[mask] = inf;
// for(int i = 0; i < g; i++) {
// if(((1<<i)&mask) == 0) continue;
// int mask1 = mask-(1<<i);
// dbl ans1 = dp[mask1];
// int sz = pos[i].size();
// for(int j = 1; j <= pos[i].size(); j++) {
// int x = pos[i][j-1];
// ans1+= min(pf[mask1][x]+((dbl) j-1)/2, pf[mask1][n]-pf[mask1][x]+((dbl) sz-j)/2);
// // cout << " " << min(pf[mask1][x]+((dbl) j-1)/2, pf[mask1][n]-pf[mask1][x]+((dbl) pos[i].size()-j)/2) << endl;
// }
// dp[mask] = min(dp[mask],ans1);
// // cout << mask << " " << i << " = " << ans1 << " " << pf[mask1][1] << endl;
// }
}
cout.setf(ios::fixed);
cout.precision(10);
cout << dp[(1<<g)-1] << endl;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
}
Compilation message
passes.cpp: In function 'void solve()':
passes.cpp:134:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int j = ans+1; j <= pos[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 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 |
340 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 |
Correct |
0 ms |
340 KB |
found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 |
Correct |
3 ms |
2124 KB |
found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 |
Correct |
4 ms |
2252 KB |
found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 |
Correct |
4 ms |
2252 KB |
found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 |
Correct |
4 ms |
2252 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 |
Incorrect |
1 ms |
1620 KB |
1st numbers differ - expected: '1023.0000000000', found: '965.5000000000', error = '0.0562072336' |
4 |
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 |
Incorrect |
1 ms |
1620 KB |
1st numbers differ - expected: '1023.0000000000', found: '965.5000000000', error = '0.0562072336' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 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 |
340 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 |
Correct |
0 ms |
340 KB |
found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 |
Correct |
3 ms |
2124 KB |
found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 |
Correct |
4 ms |
2252 KB |
found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 |
Correct |
4 ms |
2252 KB |
found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 |
Correct |
4 ms |
2252 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 |
Incorrect |
1 ms |
1620 KB |
1st numbers differ - expected: '1023.0000000000', found: '965.5000000000', error = '0.0562072336' |
13 |
Halted |
0 ms |
0 KB |
- |