//ᓚᘏᗢ
#include <bits/stdc++.h>
using namespace std;
#define int long long
int pr[15][15][100000];
int sf[15][15][100000];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
string s; cin >> s;
vector<vector<int>> g(15);
int n = s.size();
for(int i=0; i<n; i++){
g[s[i]-'A'].push_back(i);
}
vector pref(15, vector(n, 0));
for(int i=0; i<15; i++){
for(int l=0; l<15; l++){
if(i==l) continue;
for(auto u: g[i]){
pr[l][i][u]=1;
sf[l][i][u]=1;
}
for(int j=1; j<n; j++){
pr[l][i][j]+=pr[l][i][j-1];
sf[l][i][n-j-1]+=sf[l][i][n-j];
}
int s = g[l].size();
for(int j=1; j<s; j++){
pr[l][i][g[l][j]]+=pr[l][i][g[l][j-1]];
sf[l][i][g[l][s-j-1]]+=sf[l][i][g[l][s-j]];
}
}
}
vector dp(1<<15, 1e18);
dp[0] = 0;
auto pf=[&](int x){
return (double)((double)x*(double)(x-1))/(double)4.0;
};
auto val =[&](int mask, int pos, int ne){
return (0.0);
double ans = 0;
for(int i=0; i<15; i++){
if((1<<i)&mask){
if(pos-1>=0&&pos-1<g[ne].size())
ans+=pr[ne][i][g[ne][pos-1]];
if(pos<g[ne].size()&&pos>=0)
ans+=sf[ne][i][g[ne][pos]];
}
}
return (double)pf(pos)+(double)pf(g[ne].size()-pos)+(double)ans;
};
auto get =[&](int mask, int ne){
int l= 0, r = g[ne].size();
int h = 2000;
if(g[ne].size()==0) return 0.0;
/* while(h--&&l+2<r){
int m1 = l+(r-l)/3; int m2 = r-(r-l)/3;
double val1 = val(mask, m1, ne); double val2 = val(mask, m2, ne);
// if(mask==0&&ne==2) cout<<l<<" "<<r<<"\n";
if(val1 < val2) r = m2;
else l = m1;
}*/
while(val(mask, l+1, ne)<=val(mask, l, ne)){
l++;
}
/* if(val(mask, 0, ne)<val(mask, l, ne)) l=0;
if(val(mask, g[ne].size(), ne) <val(mask, l, ne)) l=g[ne].size();*/
// if(mask==0&&ne==2) cout<<l<<" "<<r<<" "<<val(mask, 0, ne)<<" "<<val(mask, 1, ne)<<"\n";
return val(mask, l, ne);
};
for(int i=1; i<(1<<15); i++){
for(int l=0; l<15; l++){
if((1<<l)&i){
dp[i]=min(dp[i], (double)dp[i^(1<<l)]+(double)get(i^(1<<l), l));
}
}
}
// cout<<dp[4];
cout<<fixed<<setprecision(5)<<dp[(1<<15)-1];
}
Compilation message
passes.cpp: In lambda function:
passes.cpp:57:35: 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]
57 | if(pos-1>=0&&pos-1<g[ne].size())
| ~~~~~^~~~~~~~~~~~~
passes.cpp:59:23: 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]
59 | if(pos<g[ne].size()&&pos>=0)
| ~~~^~~~~~~~~~~~~
passes.cpp: In lambda function:
passes.cpp:68:19: warning: unused variable 'r' [-Wunused-variable]
68 | int l= 0, r = g[ne].size();
| ^
passes.cpp:69:13: warning: unused variable 'h' [-Wunused-variable]
69 | int h = 2000;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2032 ms |
64600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2035 ms |
82524 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2035 ms |
82524 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2032 ms |
64600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
