Submission #335802

#	Time	Username	Problem	Language	Result	Execution time	Memory
335802		aanastasov	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1400 ms	76432 KiB

tickets

#include "tickets.h"
#include <algorithm>
#include <cassert>
#include <vector>
#include <set>

long long find_maximum(int numRounds, std::vector<std::vector<int>> ticket) {
    int numColors = ticket.size();
    int numRanks = ticket[0].size();
    auto plusCount = std::vector<int>(numColors, 0);
    auto minusCount = std::vector<int>(numColors, 0);
    for (int color = 0; color < numColors; ++color) {
        if (color % 2 == 0)
            plusCount[color] = numRounds;
        else
            minusCount[color] = numRounds;
    }
    auto getPlusToMinus = [&](int color) -> int {
        assert(plusCount[color] > 0);
        int plusValue = ticket[color][numRanks - 1 - (plusCount[color] - 1)];
        int minusValue = ticket[color][minusCount[color]];
        return -(plusValue + minusValue);
    };
    auto getMinusToPlus = [&](int color) -> int {
        assert(minusCount[color] > 0);
        int plusValue = ticket[color][numRanks - 1 - plusCount[color]];
        int minusValue = ticket[color][minusCount[color] - 1];
        return plusValue + minusValue;
    };

    auto plusToMinus = std::set<std::pair<int, int>>();
    auto minusToPlus = std::set<std::pair<int, int>>();
    for (int color = 0; color < numColors; ++color) {
        if (minusCount[color] > 0) {
            minusToPlus.insert({-getMinusToPlus(color), color});  // want largest one
        }
        if (plusCount[color] > 0) {
            plusToMinus.insert({-getPlusToMinus(color), color}); // want smallest one
        }
    }
    while (true) {
        // Iterate over the set of feasible solutions,
        // and do swaps as long as they are net profitable.
        auto minusToPlusItem = *minusToPlus.begin();
        auto plusToMinusItem = *plusToMinus.begin();
        // Step 1: Erase all items that involve the two colors.
        minusToPlus.erase(minusToPlusItem);
        if (plusCount[minusToPlusItem.second] > 0)
            plusToMinus.erase({-getPlusToMinus(minusToPlusItem.second), minusToPlusItem.second});
        plusToMinus.erase(plusToMinusItem);
        if (minusCount[plusToMinusItem.second] > 0)
            minusToPlus.erase({-getMinusToPlus(plusToMinusItem.second), plusToMinusItem.second});
        // Step 2: Check if doing the swap is profitable.
        minusToPlusItem.first = -minusToPlusItem.first;
        plusToMinusItem.first = -plusToMinusItem.first;
        if (minusToPlusItem.first + plusToMinusItem.first <= 0)
            break;
        // Step 3: Do the swap.
        int color1 = minusToPlusItem.second;
        int color2 = plusToMinusItem.second;
        minusCount[color1]--;
        plusCount[color1]++;
        minusCount[color2]++;
        plusCount[color2]--;
        // Step 4: Update the data structures with the new swap candidates.
        for (int color : {color1, color2}) {
            if (minusCount[color] > 0) {
                minusToPlus.insert({-getMinusToPlus(color), color});  // want largest one
            }
            if (plusCount[color] > 0) {
                plusToMinus.insert({-getPlusToMinus(color), color}); // want smallest one
            }
        }
    }
    long long res = 0;
    for (int color = 0; color < numColors; ++color) {
        assert(plusCount[color] + minusCount[color] == numRounds);
        for (int index = 0; index < minusCount[color]; ++index) res -= ticket[color][index];
        for (int index = 0; index < plusCount[color]; ++index) res += ticket[color][numRanks - 1 - index];
    }

    auto answer = std::vector<std::vector<int>>(numColors, std::vector<int>(numRanks, -1));
    auto countPerRound = std::vector<std::pair<int, int>>();
    for (int round = 0; round < numRounds; ++round) countPerRound.push_back({0, round});

    // Step 5: Construct the actual assignment of tickets.
    auto plusColors = std::vector<int>(numColors);
    for (int color = 0; color < numColors; ++color) plusColors[color] = color;
    for (int round = 0; round < numRounds; ++round) {
        std::sort(plusColors.begin(), plusColors.end(), [&](int lhs, int rhs) -> bool {
            return plusCount[lhs] > plusCount[rhs];
        });
        auto marked = std::vector<bool>(numColors, false);
        for (int index = 0; index < numColors / 2; ++index) {
            int color = plusColors[index];
            assert(plusCount[color] > 0);
            answer[color][numRanks - 1 - (plusCount[color] - 1)] = round;
            --plusCount[color];
            marked[color] = true;
        }
        for (int color = 0; color < numColors; ++color) if (!marked[color]) {
            assert(minusCount[color] > 0);
            answer[color][minusCount[color] - 1] = round;
            --minusCount[color];
        }
    }
	allocate_tickets(answer);

    return res;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10