/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
const int N = 1e5 + 100, K = 15;
int n;
double pref[K][K][N], suf[K][K][N];
string s;
double dp[N];
vector<int> v[K], vis;
void solve(){
cin >> s; n = s.length();
for(int i = 0; i < n; ++i) v[s[i]-'A'].push_back(i);
for(int i = 0; i < (1<<K); ++i) dp[i] = 1e15;
dp[0] = 0;
for(int i = 0; i < K; ++i){
for(int j = 0; j < K; ++j){
if(i == j) continue;
for(int k = 0; k <= v[i].size() + 1; ++k) pref[i][j][k] = suf[i][j][k] = 0;
int cur = 0;
double sum = 0;
for(int k = 0; k <= v[i].size(); ++k){
while(k > 0 && cur < v[j].size() && v[j][cur] < v[i][k - 1]){
cur++;
}
sum += cur;
pref[i][j][k] = sum + k * (k-1) / 4.0;
}
cur = v[j].size();
sum = 0;
for(int k = v[i].size(); k >= 1; --k){
while(cur - 1 >= 0 && v[j][cur - 1] > v[i][k - 1]){
cur--;
}
sum += v[j].size() - cur;
long long s = v[i].size() - k + 1;
suf[i][j][k] = sum + s * (s-1) / 4.0;
}
}
}
for(int mask = 1; mask < (1<<K); ++mask){
vector<int> p;
for(int j = 0; j < K; ++j){
if(mask&(1<<j)){
p.push_back(j);
}
}
int s = p.size();
for(int i = 0; i < s; ++i){
int S = v[i].size();
int l = 0, r = S;
double sum = 0;
while(l <= r){
int m1 = l + (r-l)/3, m2 = r - (r-l)/3;
double val1 = 0, val2 = 0;
for(int j = 0; j < s; ++j){
if(i==j) continue;
val1 += pref[p[i]][p[j]][m1] + suf[p[i]][p[j]][m1 + 1];
val2 += pref[p[i]][p[j]][m2] + suf[p[i]][p[j]][m2 + 1];
}
sum = min(val1, val2);
if(val1 > val2){
l = m1 + 1;
}else if(val2 > val1){
r = m2 - 1;
}else{
l = m1 + 1, r = m2 - 1;
}
}
dp[mask] = min(dp[mask], dp[mask^(1<<p[i])] + sum);
}
}
cout << dp[(1<<K)-1];
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int T = 1, aa;
// cin >> T;aa=T;
setp();
while(T--){
// cout << "Case #" << aa-T << ": ";
solve();
}
return 0;
}
Compilation message
passes.cpp: In function 'void solve()':
passes.cpp:27:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int k = 0; k <= v[i].size() + 1; ++k) pref[i][j][k] = suf[i][j][k] = 0;
| ~~^~~~~~~~~~~~~~~~~~
passes.cpp:32:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int k = 0; k <= v[i].size(); ++k){
| ~~^~~~~~~~~~~~~~
passes.cpp:33:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | while(k > 0 && cur < v[j].size() && v[j][cur] < v[i][k - 1]){
| ~~~~^~~~~~~~~~~~~
passes.cpp: In function 'int main()':
passes.cpp:98:16: warning: unused variable 'aa' [-Wunused-variable]
98 | int T = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
3156 KB |
1st numbers differ - expected: '100800.5000000000', found: '0.0000000000', error = '1.0000000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
2900 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
| 2 |
Incorrect |
23 ms |
2900 KB |
1st numbers differ - expected: '1225.0000000000', found: '0.0000000000', error = '1.0000000000' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
2900 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
| 2 |
Incorrect |
23 ms |
2900 KB |
1st numbers differ - expected: '1225.0000000000', found: '0.0000000000', error = '1.0000000000' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
3156 KB |
1st numbers differ - expected: '100800.5000000000', found: '0.0000000000', error = '1.0000000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
