This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5, MAXK=15;
const long long INF=1e18;
string s;
int n, k;
vector<vector<int> > groups;
double geninv[MAXN+1], inv[MAXK][MAXK][MAXN+1];
double memo[(1<<MAXK)];
double dp(int mask)
{
if (memo[mask]!=-1)
return memo[mask];
if (mask==(1<<k)-1)
return memo[mask]=0;
double mintotal=INF;
for (int i=0; i<k; i++)
{
if (mask&(1<<i))
continue;
int l=0;
int r=groups[i].size();
int g=groups[i].size();
double minsum=INF;
while ((r-l)/3>0)
{
int t1=l+(r-l)/3;
int t2=r-(r-l)/3;
double sum1=0;
for (int j=0; j<k; j++)
if (mask&(1<<j))
sum1=sum1+inv[i][j][t1];
sum1=sum1+geninv[t1]+geninv[g-t1];
double sum2=0;
for (int j=0; j<k; j++)
if (mask&(1<<j))
sum2=sum2+inv[i][j][t2];
sum2=sum2+geninv[t2]+geninv[g-t2];
if (sum1<sum2)
{
minsum=min(minsum, sum1);
r=t2;
}
else
l=t1;
}
for (int t=l; t<=r; t++)
{
double sum=0;
for (int j=0; j<k; j++)
if (mask&(1<<j))
sum=sum+inv[i][j][t];
sum=sum+geninv[t]+geninv[g-t];
minsum=min(minsum, sum);
}
mintotal=min(mintotal, minsum+dp(mask|(1<<i)));
}
return memo[mask]=mintotal;
}
void calcinv(int a, int b)
{
int prefix[n]={0};
for (auto x : groups[b])
prefix[x]=1;
for (int i=1; i<n; i++)
prefix[i]=prefix[i-1]+prefix[i];
int m=prefix[n-1];
long long maininv=0;
int g=groups[a].size();
for (auto x : groups[a])
if (x!=0)
maininv=maininv+prefix[x-1];
inv[a][b][g]=maininv;
for (int j=g-1; j>=0; j--)
{
int x=groups[a][j];
if (x!=0)
maininv=maininv-prefix[x-1];
maininv=maininv+(m-prefix[x]);
inv[a][b][j]=maininv;
}
return;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> s;
n=s.size();
map<char, vector<int> > groupsbychar;
for (int i=0; i<n; i++)
groupsbychar[s[i]].push_back(i);
for (auto t : groupsbychar)
groups.push_back(t.second);
k=groups.size();
for (int i=0; i<=n; i++)
geninv[i]=(double)i*(i-1)/4;
for (int i=0; i<k; i++)
for (int j=0; j<k; j++)
if (i!=j)
calcinv(i, j);
for (int i=0; i<(1<<k); i++)
memo[i]=-1;
cout << fixed << setprecision(5) << dp(0);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |