oj.uz

Submission #601940

# Submission time Handle Problem Language Result Execution time Memory
601940 2022-07-22T12:42:54 Z JeanBombeur Boarding Passes (BOI22_passes) C++17
55 / 100
 605 ms 12632 KB 
#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("%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

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.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 596 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 18 ms 572 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 22 ms 576 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 34 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 58 ms 684 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 180 ms 10856 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Incorrect 199 ms 12632 KB 1st numbers differ - expected: '1100977812.5000000000', found: '-1046505835.5000000000', error = '1.9505240011'
8 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 552 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 62 ms 572 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 174 ms 576 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 129 ms 572 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 74 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 55 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 171 ms 568 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 97 ms 576 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 94 ms 624 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 98 ms 560 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 98 ms 556 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 92 ms 560 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 105 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 98 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 86 ms 556 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 94 ms 560 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 109 ms 556 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 552 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 62 ms 572 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 174 ms 576 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 129 ms 572 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 74 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 55 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 171 ms 568 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 97 ms 576 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 94 ms 624 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 98 ms 560 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 98 ms 556 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 92 ms 560 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 105 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 98 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 86 ms 556 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 94 ms 560 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 109 ms 556 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 52 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 57 ms 576 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 158 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 131 ms 564 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 80 ms 568 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 56 ms 556 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 142 ms 572 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 101 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 95 ms 560 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 98 ms 560 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 91 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 94 ms 560 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 109 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 102 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 86 ms 556 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 91 ms 564 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 95 ms 556 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 83 ms 1972 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 101 ms 1928 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 579 ms 2044 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 446 ms 1820 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 137 ms 1876 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 579 ms 1828 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 587 ms 2224 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 568 ms 2272 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 596 ms 2132 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 572 ms 2132 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 605 ms 2176 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 580 ms 2384 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 596 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 18 ms 572 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 22 ms 576 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 34 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 58 ms 684 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 180 ms 10856 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Incorrect 199 ms 12632 KB 1st numbers differ - expected: '1100977812.5000000000', found: '-1046505835.5000000000', error = '1.9505240011'
8 Halted 0 ms 0 KB -