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>
#define int long long
#define double long double
#define rep(i,n) for(int i =0; i<n; i++)
#define all(a) a.begin(),a.end()
using namespace std;
string s;
int n;
double f(int n)
{
return ((double) n)*((double) (n-1))/4.0;
}
string ord;
vector<double>mem;
vector<vector<int>>pos;
vector<vector<vector<int>>>insleft(15,vector<vector<int>>(15)), insright(15,vector<vector<int>>(15));
int g;
// cost to add the group gr with all members of that group with and index <= to maxi boarding on the left
double cost(int bor, int gr, int firstr)
{
double sum = 0;
sum+=f(pos[gr].size()-firstr) + f(firstr);
rep(i,g) if(((1<<i)&bor)==0) sum+=insleft[gr][i][firstr]+insright[gr][i][firstr];
return sum;
}
vector<int>lookup;
double dfs(int bor)
{
if(mem[bor]>-0.9) return mem[bor];
double sol = 1e18;
rep(i,g)
{
if(!((1<<i)&bor)) continue;
int nbor = bor^(1<<i);
if(!pos[i].size()) return mem[bor]=dfs(nbor);
int start = -1, end = pos[i].size();
while(end-start>1)
{
int c = (start+end)/2;
double l =cost(bor,i,c), r=cost(bor,i,c+1);
if(r>=l) end=c;
else start=c;
};
sol=min(sol, cost(bor,i,end)+dfs(nbor));
}
return mem[bor] = sol;
}
signed main()
{
cin.tie(0);
ios_base::sync_with_stdio(false);
cin>>s;
s.size();
n=s.size();
cout.precision(300);
char maxx=0;
rep(i,n) maxx=max(maxx, s[i]);
g=maxx-'A'+1;
pos.resize(g);
rep(i,n) pos[(s[i]-'A')].push_back(i);
rep(gr,g)
{
rep(i,g)
{
if(i==gr) continue;
insleft[gr][i].assign(pos[gr].size()+1,0);
insright[gr][i].assign(pos[gr].size()+1,0);
for(int firstr=1; firstr <= pos[gr].size(); firstr++)
{
insleft[gr][i][firstr]=insleft[gr][i][firstr-1];
while (insleft[gr][i][firstr]<pos[i].size()&&pos[i][insleft[gr][i][firstr]]<pos[gr][firstr-1]) insleft[gr][i][firstr]++;
}
for(int firstr=pos[gr].size()-1; firstr >= 0; firstr--)
{
insright[gr][i][firstr]=insright[gr][i][firstr+1];
while (insright[gr][i][firstr]<pos[i].size()&&pos[i][pos[i].size()-1-insright[gr][i][firstr]]>pos[gr][firstr]) insright[gr][i][firstr]++;
}
rep(j,pos[gr].size()) insleft[gr][i][j+1]+=insleft[gr][i][j];
for(int j=pos[gr].size()-2; j>=0; j--) insright[gr][i][j]+=insright[gr][i][j+1];
}
}
lookup.assign(g,0);
rep(i,g) lookup[i]=i;
mem.assign(1<<g,-1.0);
mem[0]=0;
cout<<dfs((1<<g)-1)<<'\n';
}
Compilation message (stderr)
passes.cpp: In function 'int main()':
passes.cpp:87:38: 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]
87 | for(int firstr=1; firstr <= pos[gr].size(); firstr++)
| ~~~~~~~^~~~~~~~~~~~~~~~~
passes.cpp:90:46: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | while (insleft[gr][i][firstr]<pos[i].size()&&pos[i][insleft[gr][i][firstr]]<pos[gr][firstr-1]) insleft[gr][i][firstr]++;
passes.cpp:95:47: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | while (insright[gr][i][firstr]<pos[i].size()&&pos[i][pos[i].size()-1-insright[gr][i][firstr]]>pos[gr][firstr]) insright[gr][i][firstr]++;
passes.cpp:5:33: 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]
5 | #define rep(i,n) for(int i =0; i<n; i++)
......
97 | rep(j,pos[gr].size()) insleft[gr][i][j+1]+=insleft[gr][i][j];
| ~~~~~~~~~~~~~~~~
passes.cpp:97:13: note: in expansion of macro 'rep'
97 | rep(j,pos[gr].size()) insleft[gr][i][j+1]+=insleft[gr][i][j];
| ^~~
# | 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... |