Submission #601950

#	Time	Username	Problem	Language	Result	Execution time	Memory
601950		JeanBombeur	Boarding Passes (BOI22_passes)	C++17	100 / 100	188 ms	37984 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];

long long NbLeft[MAX_GROUPS][MAX_PASSENGERS];
long long NbRight[MAX_GROUPS][MAX_PASSENGERS];

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;
}

void Setup() {
    for (int group = 0; group < MAX_GROUPS; group ++)
    {
        int sz = Seats[group].size();
        for (int seat = 0; seat < nbPassengers; seat ++)
        {
            int pos = -1;
            for (int jump = 1 << LOG; jump; jump >>= 1)
            {
                if (pos + jump < sz && Seats[group][pos + jump] < seat)
                    pos += jump;
            }
            NbLeft[group][seat] = ++ pos;
            NbRight[group][seat] = sz - pos;
        }
    }
    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:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%s", Passengers);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

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