Submission #929141

#	Time	Username	Problem	Language	Result	Execution time	Memory
929141		EJIC_B_KEDAX	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	710 ms	112056 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
 
using ll = long long;
 
using namespace std;
 
mt19937_64 mt(time(nullptr));
 
ll find_maximum(int k, vector<vector<int>> t) {
    int n = t.size(), m = t[0].size(), oldm = m;
    multiset<pair<int, int>> st;
    vector<vector<int>> cost(n, vector<int>(k + 1, -1));
    vector<int> ptr(n, 0);
    ll res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            res -= t[i][j];
            cost[i][j] = t[i][m - 1 - j] + t[i][k - 1 - j];
        }
    }
    for (int i = 0; i < n; i++) {
        st.emplace(-cost[i][0], i);
    }
    for (int _ = 0; _ < n * k / 2; _++) {
        auto [w, i] = *st.begin();
        st.erase(st.begin());
        res -= w;
        st.emplace(-cost[i][++ptr[i]], i);
    }
    vector<vector<int>> nt(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k - ptr[i]; j++) {
            nt[i].push_back(t[i][j]);
        }
        for (int j = ptr[i] - 1; j >= 0; j--) {
            nt[i].push_back(t[i][m - 1 - j]);
        }
    }
    t = nt;
    m = k;
    vector<int> all;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            all.push_back(t[i][j]);
        }
    }
    sort(all.begin(), all.end());
    int middle = all[all.size() / 2];
    vector<pair<ll, int>> a(n);
    vector<int> bg(n, 0), end(n, m - 1);
    vector<vector<int>> s(n, vector<int>(m, -1));
    for (int i = 0; i < n; i++) {
        a[i].first = 0;
        a[i].second = i;
        for (int j = 0; j < m; j++) {
            t[i][j] -= middle;
        }
    }
    int bgs = 0, ends = 0;
    for (int i = 0; i < n; i++) {
        for (int st = 0; st < k; st++) {
            if ((abs(t[i][bg[i]]) > abs(t[i][end[i]]) && t[i][bg[i]] <= 0) || t[i][end[i]] < 0) {
                bgs++;
                bg[i]++;
            } else {
                ends++;
                end[i]--;
            }
        }
    }
    if (bgs > ends) {
        multiset<pair<int, int>> st;
        for (int i = 0; i < n; i++) {
            for (int j = bg[i] - 1; j >= 0; j--) {
                int sw = end[i] - (bg[i] - j - 1);
                if (t[i][sw] >= 0) {
                    st.emplace(-t[i][j] - t[i][sw], i);
                }
            }
        }
        while (bgs > ends) {
            assert(!st.empty());
            bgs--;
            ends++;
            auto [w, i] = *st.begin();
            st.erase(st.begin());
            bg[i]--;
            end[i]--;
        }
    } else if (ends > bgs) {
        multiset<pair<int, int>> st;
        for (int i = 0; i < n; i++) {
            for (int j = end[i] + 1; j < m; j++) {
                int sw = bg[i] + j - end[i] - 1;
                if (t[i][sw] <= 0) {
                    st.emplace(t[i][j] + t[i][sw], i);
                }
            }
        }
        while (bgs < ends) {
            bgs++;
            ends--;
            auto [w, i] = *st.begin();
            st.erase(st.begin());
            bg[i]++;
            end[i]++;
        }
    }
    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        l[i] = bg[i];
        r[i] = m - end[i] - 1;
    }
    for (int st = 0; st < k; st++) {
        vector<int> used(n, 0);
        int bal = 0;
        for (int i = 0; i < n; i++) {
            if (l[i] == k - st) {
                used[i] = 1;
                l[i]--;
                s[i][l[i]] = st;
                bal--;
            }
            if (r[i] == k - st) {
                used[i] = 1;
                s[i][m - r[i]] = st;
                r[i]--;
                bal++;
            }
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                if (bal > 0) {
                    used[i] = 1;
                    l[i]--;
                    s[i][l[i]] = st;
                    bal--;
                } else {
                    used[i] = 1;
                    s[i][m - r[i]] = st;
                    r[i]--;
                    bal++;
                }
            }
        }
    }
    vector<vector<int>> ns(n, vector<int>(oldm, -1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k - ptr[i]; j++) {
            ns[i][j] = s[i][j];
        }
        for (int j = ptr[i] - 1; j >= 0; j--) {
            ns[i][oldm - 1 - j] = s[i][m - 1 - j];
        }
    }
    allocate_tickets(ns);
    return res;
}

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