Submission #613687

#	Time	Username	Problem	Language	Result	Execution time	Memory
613687		DanShaders	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1570 ms	100680 KiB

tickets

//Cgrader.cpp
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
 
#define x first
#define y second
using ll = long long;
using ld = long double;
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
 
const int N = 2100;
 
vector<int> pw[2][N];
vector<int> sorted[N];
 
ll find_maximum(int k, vector<vector<int>> d) {
    int n = sz(d), m = sz(d[0]);
 
    vector<tuple<int, int, int>> a;
    for (int i = 0; i < n; ++i) {
        sorted[i] = vector(m, 0);
        iota(all(sorted[i]), 0);
        stable_sort(all(sorted[i]), [&](int x, int y) {
            return d[i][x] < d[i][y];
        });
        for (int j = 0; j < m; ++j) {
            a.push_back({d[i][j], i, j});
        }
    }   
    sort(all(a));
 
    ll ans = 0;
 
    for (int i = 0; i < n * m; ++i) {
        auto [val, x, y] = a[i];
        if (sz(pw[0][x]) < k) {
            ans -= val;
            pw[0][x].push_back(y);
        }
    }
 
    set<pair<int, int>> cands;
    for (int j = 0; j < n; ++j) {
        if (!sz(pw[0][j])) {
            continue;
        }
        int cval = d[j][sorted[j][m - sz(pw[1][j]) - 1]] + d[j][pw[0][j].back()];
        cands.insert({cval, j});
    }
 
    for (int i = 0; i < n * k / 2; ++i) {
        auto [value, j] = *cands.rbegin();
        ans += value;
 
        pw[1][j].push_back(sorted[j][m - sz(pw[1][j]) - 1]);
        pw[0][j].pop_back();
 
        cands.erase(--cands.end());
 
        if (sz(pw[0][j])) {
            int cval = d[j][sorted[j][m - sz(pw[1][j]) - 1]] + d[j][pw[0][j].back()];
            cands.insert({cval, j});
        }
    }
 
    int sz0 = 0, sz1 = 0;
    for (int i = 0; i < n; ++i) {
        vector<int> indexes = pw[0][i];
        indexes.insert(end(indexes), all(pw[1][i]));
        sort(all(indexes));
        assert(unique(all(indexes)) == end(indexes));
        assert(sz(pw[0][i]) + sz(pw[1][i]) == k);
        sz0 += sz(pw[0][i]);
        sz1 += sz(pw[1][i]);
    }
    assert(sz0 == n * k / 2 && sz1 == n * k / 2);
 
    set<pair<int, int>> where;
    for (int i = 0; i < n; ++i) {
        where.insert({sz(pw[0][i]), i});
    }
 
    vector s(n, vector(m, -1));
 
    for (int i = 0; i < k; ++i) {
        set<pair<int, int>> nwhere;
        
        auto it = where.begin();
        for (int j = 0; j < n; ++j, ++it) {
            auto [val, x] = *it;
            if (2 * j >= n) {
                s[x][pw[0][x].back()] = i;
                pw[0][x].pop_back();
                nwhere.insert({val - 1, x});
            } else {
                s[x][pw[1][x].back()] = i;
                pw[1][x].pop_back();
                nwhere.insert({val, x});
            }
        }
        where = nwhere;
    }
 
    // vector<int> good(m, -1);
    // iota(end(good) - k, end(good), 0);
    // for (int i = 0; i < n; ++i) {
    //  auto c = s[i];
    //  sort(all(c));
    //  assert(good == c);
    // }
    allocate_tickets(s);
    return ans; 
}

• 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