제출 #779330

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
779330		kamelfanger83	카니발 티켓 (IOI20_tickets)	C++17	0 / 100	1 ms	212 KiB

tickets

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

#define int long long

using namespace std;

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

    vector<pair<int, int>> zs, os;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (x[i][j] == 0) zs.push_back({i, j});
            else os.push_back({i, j});
        }
    }

    ans = min((int)min(zs.size(), os.size()), n/2 * k);
    if (zs.size() < os.size()){
        int i = 0, tt = 0;
        while (!zs.empty() && i < k){
            answer[zs.back().first][zs.back().second] = i;
            answer[os.back().first][os.back().second] = i;
            tt += 2;
            if (tt == n){
                i++;
                tt = 0;
            }
        }
    }

    /*vector<int> alls;

    nth_element(alls.begin(), alls.begin() + n/2 * m, alls.end());
    int globalmedian = alls[n/2*m];

    vector<pair<int, int>> tb (n, {0, m-1});
    for (int i = 0; i < k; ++i) {
        vector<int> bgains (n);
        for (int j = 0; j < n; ++j) {
            int top = x[j][tb[j].second] - globalmedian;
            int bottom = globalmedian - x[j][tb[j].first];
            bgains[j] = bottom - top;
        }
        vector<int> inds (n);
        iota(inds.begin(), inds.end(), 0);
        nth_element(inds.begin(), inds.begin() + n/2, inds.end(), [&](int a, int b){return bgains[a] > bgains[b];});
        for (int bottom = 0; bottom < n/2; ++bottom) {
            assert(x[inds[bottom]][tb[inds[bottom]].first] <= globalmedian);
            ans += globalmedian - x[inds[bottom]][tb[inds[bottom]].first];
            answer[inds[bottom]][tb[inds[bottom]].first] = i;
            tb[inds[bottom]].first++;
        }
        for (int top = n/2; top < n; ++top) {
            assert(x[inds[top]][tb[inds[top]].second] >= globalmedian);
            ans += x[inds[top]][tb[inds[top]].second] - globalmedian;
            answer[inds[top]][tb[inds[top]].second] = i;
            tb[inds[top]].second--;
        }
    }*/

    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