제출 #1311535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311535		witek_cpp	Carnival Tickets (IOI20_tickets)	C++20	0 / 100	1 ms	348 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][wsk[i]] + x[i][k - (m - wsk[i])], i});
    vi ile(k, 0); //ile juz wzielo udzial
    int wnk = 0;
    f(i, 0, n) f(j, 0, k) wnk -= x[i][j];
    rep(_, (k * n)/2) {
        pii p1 = najw.top();
        int ind = p1.nd;
        wnk += p1.st;
        najw.pop();
        wsk[ind]--;
        if (wsk[ind] >= (m - k)) najw.push({x[ind][wsk[ind]] + x[ind][k - (m - 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;
            //cout << "Git\n";
            if (ile[ind] < (n/2)) {
                uzyte.pb(ind);
            }
        }
        tv(l, uzyte) {
            wolny.push({(k/2) - ile[l], l});
        }
    }

    f(i, 0, n) wzielismy[i] = {k - (m - wsk[i] - 1), 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;
            //cout << "lol\n";
            if (ile[ind] < (n/2)) {
                uzyte.pb(ind);
            }
        }
        tv(l, uzyte) {
            wolny.push({(k/2) - ile[l], l});
        }
    }

    allocate_tickets(ans);
    return wnk;
}

/*int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int k = 1;
    vvi x = {{5, 9}, {1, 4}, {3, 6}, {2, 7}};
    //[[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