Submission #779311

#	Time	Username	Problem	Language	Result	Execution time	Memory
779311		kamelfanger83	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	432 ms	84084 KiB

tickets

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

#define int long long

using namespace std;

long long find_maximum(signed k, vector<vector<signed>> x) {
    int n = x.size();
    int m = x[0].size();
    vector<vector<signed>> answer (n, vector<signed> (m, -1));
    vector<int> alls;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            alls.push_back(x[i][j]);
        }
    }

    nth_element(alls.begin(), alls.begin() + n/2 * m, alls.end());
    int globalmedian = alls[n/2*m];

    int ans = 0;
    vector<pair<int, int>> tb (n, {0, m-1});
    for (int i = 0; i < k; ++i) {
        vector<int> bgains (n);
        for (int j = 0; j < n; ++j) {
            int top = x[j][tb[j].second] - globalmedian;
            int bottom = globalmedian - x[j][tb[j].first];
            bgains[j] = bottom - top;
        }
        vector<int> inds (n);
        iota(inds.begin(), inds.end(), 0);
        nth_element(inds.begin(), inds.begin() + n/2, inds.end(), [&](int a, int b){return bgains[a] > bgains[b];});
        for (int bottom = 0; bottom < n/2; ++bottom) {
            assert(x[inds[bottom]][tb[inds[bottom]].first] <= globalmedian);
            ans += globalmedian - x[inds[bottom]][tb[inds[bottom]].first];
            answer[inds[bottom]][tb[inds[bottom]].first] = i;
            tb[inds[bottom]].first++;
        }
        for (int top = n/2; top < n; ++top) {
            assert(x[inds[top]][tb[inds[top]].second] >= globalmedian);
            ans += x[inds[top]][tb[inds[top]].second] - globalmedian;
            answer[inds[top]][tb[inds[top]].second] = i;
            tb[inds[top]].second--;
        }
    }

    allocate_tickets(answer);

    return ans;
}

• 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