Submission #612391

#	Time	Username	Problem	Language	Result	Execution time	Memory
612391		erekle	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	467 ms	52792 KiB

tickets

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

using namespace std;

const long long INF = 1e18;

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

	vector<vector<int>> answer(n, vector<int>(m, -1));
	long long prize = 0;

	int MAX = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			MAX = max(MAX, x[i][j]);
		}
	}
	
    int z = 0, o = 0;
    vector<int> got0(n), got1(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (x[i][j] == 0) ++z, ++got0[i];
            else ++o, ++got1[i];
        }
    }
    // have to remove (m-k)*n
    int zTarget = 0, rem = (m-k)*n;
    zTarget = (rem+(z-o))/2;
    int mnRemove = 0, mxRemove = 0; // zeros removed
    vector<int> mn(1+n), mx(1+n);
    for (int i = 0; i < n; ++i) {
        mnRemove += max(m-k-got1[i], 0);
        mxRemove += min(m-k, got0[i]);
        mn[i+1] = mnRemove;
        mx[i+1] = mxRemove;
    }

    // Recalculate realistic target
    if (zTarget < mnRemove) zTarget = mnRemove;
    if (zTarget > mxRemove) zTarget = mxRemove;

    // Remove so that target is achieved
    vector<int> removed0(n), removed1(n);
    for (int i = n; i >= 1; --i) {
        int least = max(m-k-got1[i-1], 0);
        int most = min(m-k, got0[i-1]);
        int largestAfter = mx[i-1];
        removed0[i-1] = max(zTarget-largestAfter, least);
        assert(least <= removed0[i-1] && removed0[i-1] <= most);
        removed1[i-1] = m-k-removed0[i-1];
        zTarget -= removed0[i-1];
    }

    // This is the same as the solution to m=k except one detail below
    vector<int> cnt[2], remain[2];
    cnt[0].resize(n), cnt[1].resize(n);
    remain[0].resize(n), remain[1].resize(n);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (x[i][j] == 0) ++cnt[0][i];
        }
    }
    // vector<pair<int, int>> v;
    // for (int i = 0; i < n; ++i) {
    // 	for (int j = 0; j < m; ++j) v.emplace_back(x[i][j], i);
    // }
    // sort(v.begin(), v.end());
    // for (int i = 0; (i<<1) < n*m; ++i) {
    // 	++cnt[0][v[i].second];
    // }
    for (int i = 0; i < n; ++i) {
        cnt[1][i] = m-cnt[0][i];
        remain[0][i] = cnt[0][i];
        remain[1][i] = cnt[1][i];
        // Here we are subtracting removed from remain
        remain[0][i] -= removed0[i];
        remain[1][i] -= removed1[i];
        assert(remain[0][i] >= 0 && remain[0][i] <= cnt[0][i]);
        assert(remain[1][i] >= 0 && remain[1][i] <= cnt[1][i]);
        assert(remain[0][i] + remain[1][i] == k);
    }

    for (int i = 0; i < k; ++i) {
        int used0 = 0;
        bool seen0 = false;
        for (int y = 0; y < n; ++y) {
            if (!remain[1][y]) { // zero
                if (!y) seen0 = true;
                assert(remain[0][y]);
                prize -= x[y][cnt[0][y]-remain[0][y]];
                answer[y][cnt[0][y]-remain[0][y]] = i;
                --remain[0][y];
                ++used0;
            } else if (!remain[0][y]) { // one
                if (!y) seen0 = true;
                assert(remain[1][y]);
                prize += x[y][cnt[0][y]+remain[1][y]-1];
                answer[y][cnt[0][y]+remain[1][y]-1] = i;
                --remain[1][y];
            }
        }
        for (int y = 0; y < n; ++y) { // both
            if (!remain[0][y] || !remain[1][y]) continue;
            seen0 = true;
            if (2*used0 < n) {
                prize -= x[y][cnt[0][y]-remain[0][y]];
                answer[y][cnt[0][y]-remain[0][y]] = i;
                --remain[0][y];
                ++used0;
            } else {
                prize += x[y][cnt[0][y]+remain[1][y]-1];
                answer[y][cnt[0][y]+remain[1][y]-1] = i;
                --remain[1][y];
            }
        }
        assert(seen0);
    }
	allocate_tickets(answer);
	return prize;
}

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