Submission #1226673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226673		LucaIlie	Carnival Tickets (IOI20_tickets)	C++17	76 / 100	560 ms	109308 KiB

tickets

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

using namespace std;

struct update {
    int i, j, cost;

    bool operator < (update x) {
        if (cost == x.cost)
            return j > x.j;
        return cost < x.cost;
    }
};

const int MAX_N = 1500;
int taken[MAX_N][MAX_N];
pair<int, int> tickets[MAX_N][MAX_N];
bool rounds[MAX_N][MAX_N];
vector<update> updates;

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

    long long cost = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) 
            tickets[i][j] = {x[i][j], j};
        sort(tickets[i], tickets[i] + m);
        for (int j = 0; j < k; j++) {
            cost -= tickets[i][j].first;
            taken[i][j] = 1;
        }

        for (int j = 0; j < k; j++)
            updates.push_back({i, j, tickets[i][j].first + tickets[i][m - k + j].first});
    }

    sort(updates.begin(), updates.end());
    reverse(updates.begin(), updates.end());

    for (int i = 0; i < n * k / 2; i++) {
        auto a = updates[i];
        taken[a.i][a.j] = 0;
        taken[a.i][m - k + a.j] = 2;
        cost += a.cost;
    }

    vector<vector<int>> alloc(n);
    for (int i = 0; i < n; i++) {
        alloc[i].resize(m);
        for (int j = 0; j < m; j++)
            alloc[i][j] = -1;
    }

    int r = 0;
    for (int i = 0; i < n; i++) {
        int a = 0;
        for (int j = 0; j < m; j++) {
            if (taken[i][j] > 0)
                a++;
            if (taken[i][j] == 1) {
                alloc[i][tickets[i][j].second] = r; 
                rounds[i][r] = true;
                r = (r + 1) % k;
            }
        }
        assert(a == k);
    }

    for (int i = 0; i < n; i++) {
        int r = 0;
        for (int j = 0; j < m; j++) {
            // printf("%d ", taken[i][j]);
            if (taken[i][j] == 2) {
                while (rounds[i][r])
                    r++;
                rounds[i][r] = true;
                alloc[i][tickets[i][j].second] = r; 
            }
        }
        // printf("\n");
    }

    allocate_tickets(alloc);

	return cost;
}

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