Submission #302092

#	Time	Username	Problem	Language	Result	Execution time	Memory
302092		VEGAnn	Carnival Tickets (IOI20_tickets)	C++14	0 / 100	3 ms	768 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define i2 array<int,2>
#define i3 array<int,3>
using namespace std;
typedef long long ll;
const int N = 1600;
const ll OO = 1e18;
vector<i2> elms;
vector<int> vec[N][2];
vector<int> vc[2];
ll f[N][N];
int pre[N][N];

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

	vector<vector<int>> answer;

	for (int i = 0; i < n; i++) {
		std::vector<int> row(m);

		fill(all(row), -1);

		answer.push_back(row);
	}

	ll ans = 0;

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++)
            vec[i][x[i][j]].PB(j);
    }

    for (int itr = 0; itr < k; itr++){
        vc[0].clear();
        vc[1].clear();

        for (int i = 0; i < n; i++)
            if (sz(vec[i][0]) > sz(vec[i][1]))
                vc[0].PB(i);
            else vc[1].PB(i);

        if (sz(vc[0]) > sz(vc[1])){
            elms.clear();

            for (int i = 0; i < sz(vc[0]); i++) {
                int id = vc[0][i];

                elms.PB({sz(vec[id][1]), id});
            }

            sort(all(elms));

            while (sz(elms) > sz(vc[1])){
                if (elms.back()[0] == 0) break;

                vc[1].PB(elms.back()[1]);
                elms.pop_back();
            }

            ans += min(sz(elms), sz(vc[1]));

            for (i2 cr : elms){
                int id = cr[1];

                answer[id][vec[0][id].back()] = itr;
                vec[0][id].pop_back();
            }

            for (int id : vc[1]){
                answer[id][vec[1][id].back()] = itr;
                vec[1][id].pop_back();
            }
        } else {
            elms.clear();

            for (int i = 0; i < sz(vc[1]); i++) {
                int id = vc[1][i];

                elms.PB({sz(vec[id][0]), id});
            }

            sort(all(elms));

            while (sz(elms) > sz(vc[0])){
                if (elms.back()[0] == 0) break;

                vc[0].PB(elms.back()[1]);
                elms.pop_back();
            }

            ans += min(sz(elms), sz(vc[0]));

            for (i2 cr : elms){
                int id = cr[1];

                answer[id][vec[1][id].back()] = itr;
                vec[1][id].pop_back();
            }

            for (int id : vc[0]){
                answer[id][vec[0][id].back()] = itr;
                vec[0][id].pop_back();
            }
        }
    }

    allocate_tickets(answer);

	return ans;
}

• 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