제출 #1311006

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

tickets

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

typedef long long ll;

#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define f(i, a, b) for (int i = a; i < b; i++)
#define rep(i, a) f(i, 0, a)
#define tv(a, x) for (auto& a : x)
#define DUZO 1000000000000000000LL
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

/*void allocate_tickets(vvi ans) {
    int n = sz(ans);
    int m = sz(ans[0]);
    cout << "moja odpowiedz to:\n";
    rep(i, n) {
        rep(j, m) {
            cout << ans[i][j] << " ";
        }
        cout << "\n";
    }
}*/

ll find_maximum(int k, vvi x) {
    int n = sz(x);
    int m = sz(x[0]);
    //wybieramy k * n/2 najlepszych i najgorszych
    vvi ans(n, vi(m, -1));
    priority_queue<pii> najw;
    vi wsk(n, m - 1);
    rep(i, n) najw.push({x[i].back(), i});
    vi ile(k, 0); //ile juz wzielo udzial
    int sum1 = 0;
    rep(_, (k * n)/2) {
        pii p1 = najw.top();
        int ind = p1.nd;
        sum1 += p1.st;
        najw.pop();
        wsk[ind]--;
        if (wsk[ind] >= (m - k)) najw.push({x[ind][wsk[ind]], ind});
    }
    vector<pii> wzielismy(n);
    f(i, 0, n) wzielismy[i] = {(m - 1) - wsk[i], i};
    sort(all(wzielismy));
    reverse(all(wzielismy));

    priority_queue<pii> wolny; //ile wolnych miejsc
    f(i, 0, k) wolny.push({k/2, i});

    tv(ele, wzielismy) {
        vi uzyte;
        f(j, 0, ele.st) {
            pii p1 = wolny.top();
            wolny.pop();
            int ind = p1.nd;
            ile[ind]++;
            ans[ele.nd][m - 1 - j] = ind + 1;
            if (ile[ind] < (n/2)) {
                uzyte.pb(ind);
            }
        }
        tv(l, uzyte) {
            wolny.push({(k/2) - ile[l], l});
        }
    }
    priority_queue<pii> najm;
    f(i, 0, n) wsk[i] = 0;
    rep(i, n) najm.push({-x[i][0], i});
    f(i, 0, k) ile[i] = 0;
    vi ost(k, 0); //ostatin element w naszym bloku
    int sum2 = 0;
    rep(_, (k * n)/2) {
        pii p1 = najm.top();
        sum2 = p1.st;
        int ind = p1.nd;
        najm.pop();
        wsk[ind]++;
        if (wsk[ind] < (k - 1)) najm.push({-x[ind][wsk[ind]], ind});
    }

    f(i, 0, n) wzielismy[i] = {wsk[i], i};
    sort(all(wzielismy));
    reverse(all(wzielismy));
    wolny = {};
    f(i, 0, k) wolny.push({(k/2), i});
    f(i, 0, k) ile[i] = 0;
    
    tv(ele, wzielismy) {
        vi uzyte;
        f(j, 0, ele.st) {
            pii p1 = wolny.top();
            wolny.pop();
            int ind = p1.nd;
            ile[ind]++;
            ans[ele.nd][j] = ind + 1;
            if (ile[ind] < (n/2)) {
                uzyte.pb(ind);
            }
        }
        tv(l, uzyte) {
            wolny.push({(k/2) - ile[l], l});
        }
    }

    int wnk = sum1 + sum2; //sum2 na minusie wiec essa
    allocate_tickets(ans);
    return wnk;
}

/*int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int k = 2;
    //[[0, 2, 5],[1, 1, 3]]
    vvi x = {{0, 0, 2}, {0, 0, 2}, {0, 1, 1}, {0, 0, 0}};
    int moj_ans = find_maximum(k, x);
    cout << "moja odpowiedz to " << moj_ans << "\n";
}*/

• 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