Submission #601938

#	Time	Username	Problem	Language	Result	Execution time	Memory
601938		JeanBombeur	Boarding Passes (BOI22_passes)	C++17	55 / 100	628 ms	12752 KiB

passes

#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;
    int sz = Seats[group].size();
    int 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("%f\n", DP[(1 << MAX_GROUPS) - 1] / 2.);
    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);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40