Submission #335694

#	Time	Username	Problem	Language	Result	Execution time	Memory
335694		aanastasov	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	863 ms	73268 KiB

tickets

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

#define DEBUG(x) 42; //std::cerr << #x << ": " << x << std::endl;

template<typename T> void debugVector(std::vector<T> vals, bool skip = true) {
    if (skip) return;
    std::cerr << "{";
    for (int i = 0; i < vals.size(); ++i) {
        if (i > 0) std::cerr << ", ";
        std::cerr << vals[i];
    }
    std::cerr << "}" << std::endl;
}

long long find_maximum(int numRounds, std::vector<std::vector<int>> ticket) {
    const int numColors = ticket.size();
    DEBUG(numColors);
    const int length = ticket[0].size();
    DEBUG(length);
//    assert(numRounds == 1);

    auto answer = std::vector<std::vector<int>>(numColors, std::vector<int>(length, -1));
    auto minimums = std::vector<int>(numColors, 0);
    auto maximums = std::vector<int>(numColors, length - 1);

    auto chooseTickets = [&](int colorOfB, bool isMin) -> std::pair<bool, std::vector<int>> {
        DEBUG(colorOfB);
        DEBUG(isMin);
        const int b = (isMin ? ticket[colorOfB][minimums[colorOfB]] : ticket[colorOfB][maximums[colorOfB]]);
        DEBUG(b);
        auto ticketsChosen = std::vector<int>(numColors, -1);
        ticketsChosen[colorOfB] = b;
        int numSmaller = 0;
        int numLarger = 0;
        auto choices = std::vector<std::pair<int, int>>();
        for (int color = 0; color < numColors; ++color) {
            assert(minimums[color] <= maximums[color]);
            if (color == colorOfB) continue;
            if (ticket[color][maximums[color]] < b) {
                numSmaller++; 
                ticketsChosen[color] = ticket[color][minimums[color]]; 
            } else if (b < ticket[color][minimums[color]]) { 
                numLarger++; 
                ticketsChosen[color] = ticket[color][maximums[color]]; 
            } else {
                long long minScore = llabs(ticket[color][minimums[color]] - b);
                long long maxScore = llabs(ticket[color][maximums[color]] - b);
                choices.push_back({maxScore - minScore, color});
            }
        }
        debugVector(ticketsChosen);
        DEBUG(numLarger);
        DEBUG(numSmaller);
        std::sort(choices.begin(), choices.end());
        if (numLarger > numColors / 2 || numSmaller > numColors / 2 - 1) {
            return {false, std::vector<int>()};
        }
        int index = choices.size() - 1;
        while (numLarger < numColors / 2) {
            auto item = choices[index];
            index--;
            ticketsChosen[item.second] = ticket[item.second][maximums[item.second]];
            numLarger++;
        }
        assert(numLarger == numColors / 2);
        while (index >= 0) {
            auto item = choices[index];
            ticketsChosen[item.second] = ticket[item.second][minimums[item.second]];
            index--;
            numSmaller++;
        }
        assert(numSmaller == numColors / 2 - 1);
        for (auto x : ticketsChosen) assert(x != -1);
        return {true, ticketsChosen};
    };

    auto evaluate = [](int b, std::vector<int>& chosenTickets) -> long long {
        long long res = 0;
        for (auto &x : chosenTickets) res += llabs(b - x);
        return res;
    };

    long long totalScore = 0;
    for (int round = 0; round < numRounds; ++round) {
        auto bestB = std::pair<int, bool>(-1, false);
        auto bestScore = -1LL;
        for (int isMin = 0; isMin <= 1; ++isMin)
            for (int color = 0; color < numColors; ++color) {
                auto output = chooseTickets(color, isMin > 0 ? true : false);
                DEBUG(output.first);
                if (!output.first) continue;
                const int b = isMin > 0 ? ticket[color][minimums[color]] : ticket[color][maximums[color]];
//                std::cerr << "if we choose b = " << b << ": "; debugVector(output.second);
                auto score = evaluate(b, output.second);
                if (score > bestScore) {
                    bestScore = score;
                    bestB = {color, isMin > 0 ? true : false};
                }
            }
        assert(bestScore >= 0);
        totalScore += bestScore;
        auto output = chooseTickets(bestB.first, bestB.second);
        assert(output.first);
        for (int color = 0; color < numColors; ++color) {
            if (output.second[color] == ticket[color][minimums[color]]) {
                answer[color][minimums[color]] = round;
                minimums[color]++;
            } else {
                answer[color][maximums[color]] = round;
                maximums[color]--;
            }
        }
    }
    
    allocate_tickets(answer);
    return totalScore;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define DEBUG(x) 42; //std::cerr << #x << ": " << x << std::endl;
      |                  ^~
tickets.cpp:21:5: note: in expansion of macro 'DEBUG'
   21 |     DEBUG(numColors);
      |     ^~~~~
tickets.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define DEBUG(x) 42; //std::cerr << #x << ": " << x << std::endl;
      |                  ^~
tickets.cpp:23:5: note: in expansion of macro 'DEBUG'
   23 |     DEBUG(length);
      |     ^~~~~
tickets.cpp: In lambda function:
tickets.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define DEBUG(x) 42; //std::cerr << #x << ": " << x << std::endl;
      |                  ^~
tickets.cpp:31:9: note: in expansion of macro 'DEBUG'
   31 |         DEBUG(colorOfB);
      |         ^~~~~
tickets.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define DEBUG(x) 42; //std::cerr << #x << ": " << x << std::endl;
      |                  ^~
tickets.cpp:32:9: note: in expansion of macro 'DEBUG'
   32 |         DEBUG(isMin);
      |         ^~~~~
tickets.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define DEBUG(x) 42; //std::cerr << #x << ": " << x << std::endl;
      |                  ^~
tickets.cpp:34:9: note: in expansion of macro 'DEBUG'
   34 |         DEBUG(b);
      |         ^~~~~
tickets.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define DEBUG(x) 42; //std::cerr << #x << ": " << x << std::endl;
      |                  ^~
tickets.cpp:56:9: note: in expansion of macro 'DEBUG'
   56 |         DEBUG(numLarger);
      |         ^~~~~
tickets.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define DEBUG(x) 42; //std::cerr << #x << ": " << x << std::endl;
      |                  ^~
tickets.cpp:57:9: note: in expansion of macro 'DEBUG'
   57 |         DEBUG(numSmaller);
      |         ^~~~~
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:7:18: warning: statement has no effect [-Wunused-value]
    7 | #define DEBUG(x) 42; //std::cerr << #x << ": " << x << std::endl;
      |                  ^~
tickets.cpp:94:17: note: in expansion of macro 'DEBUG'
   94 |                 DEBUG(output.first);
      |                 ^~~~~
tickets.cpp: In instantiation of 'void debugVector(std::vector<T>, bool) [with T = int]':
tickets.cpp:55:34:   required from here
tickets.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 0; i < vals.size(); ++i) {

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