Submission #1061651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061651		vjudge1	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	717 ms	100180 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ll = long long;
using ii = pair<int, int>;
using vll = vector<ll>;

ll find_maximum(int k, vector<vi> x) {
	int n = x.size();
	int m = x[0].size();
    vll Sum(n, 0), CntPlus(n, 0);
    auto calc = [&](int cul, int nr) { // cat as castiga
        return x[cul][m - 1 - nr] + x[cul][k - 1 - nr];
    };
    priority_queue<pair<ll, int> > PQ;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < k; ++j) {
            Sum[i] -= x[i][j];
        }
        PQ.push({calc(i, 0), i});
    }
    for(int nr = 0; nr < n * k / 2; ++nr) {
        auto [delta, cul] = PQ.top();
        PQ.pop();
        ++CntPlus[cul];
        Sum[cul] += delta;
        if(CntPlus[cul] < k) {
            PQ.push({calc(cul, CntPlus[cul]), cul});
        }
    }
    ll re = 0;
    for(auto it : Sum) re += it;

    vector<vector<ii>> Plus(n), Minus(n);

    vector<vi> S(n, vi(m, -1));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < k - CntPlus[i]; ++j)
            Minus[i].push_back({i, j});
        for(int j = 0; j < CntPlus[i]; ++j)
            Plus[i].push_back({i, m - 1 - j});
    }
    for(int nr = 0; nr < k; ++nr) {
        vi Neutre;
        vector<ii> Luate;
        int sum = 0;
        vi ord;
        for(int i = 0; i < n; ++i) {
            ord.push_back(i);
        }
        sort(ord.begin(), ord.end(), [&](auto a, auto b) {
            return abs((int)Plus[a].size() - (int)Minus[a].size()) 
            > abs((int)Plus[b].size() - (int)Minus[b].size());
        });
        for(int i = 0; i < n; ++i) {
            int it = ord[i], ramase = n - i;
            if((sum != ramase && Plus[it].size() > Minus[it].size()) || sum == -ramase) {
                Luate.push_back(Plus[it].back());
                Plus[it].pop_back();
                ++sum;
            } else {
                Luate.push_back(Minus[it].back());
                Minus[it].pop_back();
                --sum;
            }
        }
        vi Val;
        for(auto [c, p] : Luate) {
            S[c][p] = nr;
            Val.push_back(x[c][p]);
        }
    }
    allocate_tickets(S);
    return re;
}

• 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