Submission #479000

#	Time	Username	Problem	Language	Result	Execution time	Memory
479000		khoabright	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	868 ms	76664 KiB

tickets

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

//#define int long long 
#define ff first
#define ss second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define mp make_pair
#define vii vector<vector<int>>
#define ll long long 

void allocate_tickets(vii a);

struct ticket{
    int color, order, value;
};

bool operator < (const ticket &x, const ticket &y) {
    if (x.value == y.value) {
        return mp(x.color, x.order) < mp(y.color, y.order);
    }
    return x.value < y.value;
}  

ll find_maximum(int k, vii a) {
    int n = a.size(), m = a[0].size();
    vii allo(n, vector<int> (m));
    
    ll prize = 0;
    vector<ticket> Replace;
    vector<int> Plus(n + 1, k);

    rep(i, 0, n - 1) {
        rep1(j, m - 1, m - k) {
            prize += a[i][j];
            allo[i][j] = 1;
        }

        rep(j, 0, k - 1) {
            ticket tmp;
            tmp.color = i;
            tmp.order = j;
            tmp.value = a[i][j] + a[i][m - k + j];
            Replace.push_back(tmp);
        }
    }

    sort(all(Replace));
    
    rep(i, 1, k * (n / 2)) {
        auto [color, order, value] = Replace[i - 1];
        prize -= value;

        --Plus[color];            
        allo[color][m - k + order] = 0;
        allo[color][order] = -1;
    }

    vector<int> v(n);
    rep(i, 0, n - 1) v[i] = i;

    sort(all(v), [&](int x, int y) {
        return Plus[x] < Plus[y];
    });

    int start = -1;
    rep(ii, 0, n - 1) {
        int i = v[ii];

        vector<bool> used(m);

        rep(j, 0, m - 1) {
            if (allo[i][j] != -1) break;
            start = (start + 1) % k;
            allo[i][j] = start + 1;
            used[start] = 1;
        }

        int fin = 0;
        rep1(j, m - 1, 0) {
            if (allo[i][j] != 1) break;
            while (fin < k && used[fin]) ++ fin;
            if (fin >= k) break;
            allo[i][j] = fin + 1;
            ++fin;
        }
    }
    

    rep(i, 0, n - 1) rep(j, 0, m - 1) --allo[i][j];

    allocate_tickets(allo);
    return prize;
}

• 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