#pragma GCC optimize("Ofast,inline,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")//,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int inf = int(1e18);
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;
#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define per(i, high) for (int i = high-1; i >= 0; i--)
#define _LOCAL _MSC_VER
#if _LOCAL > 0
#define deb __debugbreak();
#define assert(x) debassert(x)
#define popcount(x) __popcnt(x)
#define clz(x) _lzcnt_u32(x)
#else
#define clz(x) __builtin_clz(x)
#define deb ;
#define popcount(x) __builtin_popcountll(x)
#endif
inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
#ifdef _DEBUG
#define debassert(expr) if(!(expr)) deb;
#else
#define debassert(expr) ;
#endif
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define setcontains(set, x) (set.find(x) != set.end())
#define sz(container) ((int)container.size())
vector<p2> dirs = { {0,1},{0,-1},{1,0},{-1,0} };
// time and rng
auto Start = chrono::high_resolution_clock::now();
void resettimer() { Start = chrono::high_resolution_clock::now(); }
int elapsedmillis() { return chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - Start).count(); }
random_device rd;
mt19937 rng(rd());
template<typename T, typename U> inline int randint(T lo, U hi) { return uniform_int_distribution<int>((int)lo, (int)hi)(rng); } // [lo,hi]
template<typename T> inline T randel(vector<T>& v) { return v[uniform_int_distribution<int>(int(0), int(v.size()) - int(1))(rng)]; } // [lo,hi]
signed main()
{
fast();
string s;
cin >> s;
map<char, int> gind;
vvi groups;
vvi activegroup;
int n = sz(s);
rep(i, n)
{
if (!setcontains(gind, s[i])) gind[s[i]] = gind.size(), groups.push_back({});
groups[gind[s[i]]].push_back(i);
}
int g = sz(groups);
vi perm(g);
rep(i, g)perm[i] = i;
vi groupsz(g);
rep(i, g)groupsz[i] = sz(groups[i]);
activegroup.resize(g, vi(n));
rep(i, g) repe(v, groups[i]) activegroup[i][v] = 1;
double ans = inf;
vector<double> exppl(n);
double v = 0;
double addend = 0;
repp(i, 1, n)
{
v += addend;
addend += 0.5;
exppl[i] = v;
}
auto solvegroup = [&](int groupid, vi& active)
{
double best = inf;
rep(p, groupsz[groupid] + 1)
{
double cost = 0;
int mid = (p == groupsz[groupid] ? n : groups[groupid][p]);
int pref = 0;
rep(i, mid)
{
if (active[i]) pref += 1;
if (activegroup[groupid][i]) cost += pref;
}
pref = 0;
for (int i = n - 1; i >= mid; i--)
{
if (active[i]) pref += 1;
if (activegroup[groupid][i]) cost += pref;
}
best = min(best, cost + exppl[p] + exppl[groupsz[groupid] - p]);
}
return best;
};
do
{
vi active(n);
double cost = 0;
rep(i, g)
{
int groupid = perm[i];
cost += solvegroup(groupid, active);
repe(v, groups[groupid]) active[v] = 1;
}
ans = min(ans, cost);
} while (next_permutation(all(perm)));
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
348 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 |
0 ms |
348 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
| 2 |
Incorrect |
1 ms |
348 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 |
0 ms |
348 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
| 2 |
Incorrect |
1 ms |
348 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 |
3 ms |
348 KB |
1st numbers differ - expected: '100800.5000000000', found: '0.0000000000', error = '1.0000000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
