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 <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
// <|°_°|>
// M. Broccoli
const int MAX_GROUPS = (15);
const int MAX_PASSENGERS = (1e5 + 1);
const int LOG = 16;
long long DP[1 << MAX_GROUPS];
vector <long long> Cost[MAX_GROUPS][MAX_GROUPS];
char Passengers[MAX_PASSENGERS];
vector <int> Seats[MAX_GROUPS];
int nbPassengers;
void Read() {
scanf("%s", Passengers);
nbPassengers = strlen(Passengers);
for (int i = 0; i < nbPassengers; i ++)
{
Seats[Passengers[i] - 'A'].push_back(i);
}
return;
}
long long NbLeft(int group, int seat) {
int pos = -1;
int sz = Seats[group].size();
for (int jump = 1 << LOG; jump; jump >>= 1)
{
if (pos + jump < sz && Seats[group][pos + jump] < seat)
pos += jump;
}
return ++ pos;
}
long long NbRight(int group, int seat) {
return Seats[group].size() - NbLeft(group, seat);
}
void Setup() {
for (int set = 0; set < MAX_GROUPS; set ++)
{
for (int nouv = 0; nouv < MAX_GROUPS; nouv ++)
{
int sz = Seats[nouv].size();
long long sum = 0;
for (int i = 0; i < sz; i ++)
{
sum += NbRight(set, Seats[nouv][i]);
}
Cost[set][nouv].push_back(sum);
for (int cut = 0; cut < sz; cut ++)
{
sum += NbLeft(set, Seats[nouv][cut]) - NbRight(set, Seats[nouv][cut]);
Cost[set][nouv].push_back(sum);
}
}
}
return;
}
bool GoLeft(int mask, int group, int cut) {
int sz = Seats[group].size();
int cur = Seats[group][cut];
long long left = cut, right = sz - cut - 1;
for (int i = 0; i < MAX_GROUPS; i ++)
{
if ((mask >> i) & 1)
{
left += 2 * NbLeft(i, cur);
right += 2 * NbRight(i, cur);
}
}
return left < right;
}
int FindCut(int mask, int group) {
int cut = -1;
int sz = Seats[group].size();
for (int jump = 1 << LOG; jump; jump >>= 1)
{
if (cut + jump < sz && GoLeft(mask, group, cut + jump))
cut += jump;
}
return ++ cut;
}
long long CostTransi(int mask, int group) {
long long sum = 0;
long long sz = Seats[group].size();
long long cut = FindCut(mask, group);
for (int i = 0; i < MAX_GROUPS; i ++)
{
if ((mask >> i) & 1)
sum += 2 * Cost[i][group][cut];
}
sum += (cut * (cut - 1)) / 2 + ((sz - cut) * (sz - cut - 1)) / 2;
return sum;
}
void Solve() {
fill_n(DP, 1 << MAX_GROUPS, 1LL << 60);
DP[0] = 0;
for (int mask = 0; mask < (1 << MAX_GROUPS); mask ++)
{
for (int i = 0; i < MAX_GROUPS; i ++)
{
if (!((mask >> i) & 1))
DP[mask ^ (1 << i)] = min(DP[mask ^ (1 << i)], DP[mask] + CostTransi(mask, i));
}
}
printf("%lld", DP[(1 << MAX_GROUPS) - 1] / 2);
if (DP[(1 << MAX_GROUPS) - 1] & 1)
printf(".5");
printf("\n");
return;
}
int main() {
Read();
Setup();
Solve();
return 0;
}
Compilation message (stderr)
passes.cpp: In function 'void Read()':
passes.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | scanf("%s", Passengers);
| ~~~~~^~~~~~~~~~~~~~~~~~
# | 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... |