Submission #1012781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012781		ProtonDecay314	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	815 ms	132276 KiB

tickets

/*

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

#ifndef DEBUG
#include "tickets.h"
#endif

#ifdef DEBUG
vvi ta;
void allocate_tickets(const vvi& a_ta) {
    LI(i, 0, (int)ta.size()) {

        copy(a_ta[i].begin(), a_ta[i].end(), back_inserter(ta[i]));
    }
}
#endif

ll find_maximum(int k, vvi x) {
    int n = x.size(), m = x[0].size();
    vvi talloc;
    LI(i, 0, n) {
        vi tallocr(m, -1);
        talloc.pb(tallocr);
    }

    ll ans = 0ll;

    /*
    It's time to full point this problem! >:D

    So uhh

    for each color, pick k tickets
    it's always optimal to pick a prefix/suffix

    Tapos, the total number of "max" tickets must equal kn / 2
    Same for min tickets

    same thing as subtask 1, let's start with like, all mins

    Then, we pair each minimum with the maximum

    tapos, the oppcost is just min + max again, since by removing a min we increase by that value,
    tapos we increase by max ulit, so the net effect is just the sum of min + max

    Hmm, wait, is it possible, given some initial picking of max and min, that we can assign the k rounds
    so that it works??

    hmm

    +00000
    +++000
    +++++0
    0-----
    000---
    00000-
    
    +00000|0-----
    ++0000|10----
    ++++++|210122
    0-----|-22211
    00----|--1000
    000000|------

    Consider nk points. Now, consider the median line

    Oh, we can do some kind of pqueue siguro, no? haha

    or kailangan ba? hmm, kasi like, pwede naman i-sort ulit
    in O(n log n)

    Tapos, we have k rounds, so O(k n log n) siya

    Finally, since k is O(m), the final complexity is O(mn log n),
    which works naman. No need for pqueue, pampasakit lamang yun sa ulo para sa
    implementation haha (baka sumabog pa ang utak ko lol)

    also why am I suddenly writing Taglish LOL

    ANYWAYS, that handles the assignment part of the problem

    now, we need to quickly construct the subset, haha

    paano yun though?

    so, for every color, there is a corresponding opportunity cost
    (wow, just like in economics, where every decision has a corresponding opportunity cost)
    
    o, tapos, i-max-pqueue nalang natin yung <min + max> per color, then repeat the process kn/2 times

    finally, kung may kulay na wala nang min tickets, assign it a cost of like -infinity or just remove it from the pqueue
    actually, wait, kailangan nga ba ng pqueue? idts 
    */

    // Augment x with indices

    vvpi xwind;
    xwind.reserve(n);
    LI(i, 0, n) {
        vpi xwindr;
        xwindr.reserve(m);
        LI(j, 0, m) {
            xwindr.pb({x[i][j], j});
        }
        sort(xwindr.begin(), xwindr.end());

        xwind.pb(xwindr);
    }

    // Representation: pair<opcost :: ll, inds :: pi>, tapos sort it decreasing
    typedef pair<ll, pi> opcost;
    vector<opcost> opcosts; // Thanks again MA'AM BAMBIE

    LI(i, 0, n) {
        LI(j, 0, k) {
            int t1 = xwind[i][j].fi, t2 = xwind[i][j - k + m].fi;
            opcosts.pb({t1 + t2, {i, j}});
        }
    }

    sort(opcosts.begin(), opcosts.end(), greater<opcost>()); // It's time to be greedy

    typedef vector<deque<int>> picked_t;
    picked_t picked; // ! normal_i_ind -> xwind_j_ind (need to convert sorted ind "xwind_j_ind" to normal ind, this should be accessible from xwind naman)
    vpi num_max;
    LI(i, 0, n) {
        deque<int> picked_r;
        picked.pb(picked_r);
        num_max.pb({0, i});
    }

    LI(i, 0, k * n) {
        // Mark these to be done greedily
        auto [_, ind_pair] = opcosts[i]; // Man, I wished we had auto [_, [i1, i2]] for structured bindings, like in JavaScript :(
        auto [i1, i2] = ind_pair;

        bool is_max = i < ((k * n) >> 1);
        int picked_ind = is_max ? i2 - k + m : i2; // ! lots of math, check this again!

        picked[i1].push_front(picked_ind);

        if(is_max) num_max[i1].fi++;

        ans = ans + (is_max ? (ll)xwind[i1][picked_ind].fi : -(ll)xwind[i1][picked_ind].fi);
    }

    // Eyoo, it passes sample test case??

    // Allocation time

    LI(i, 0, k) {
        // Sort the colors by number of maxes to assign
        sort(num_max.begin(), num_max.end(), greater<pi>());
        LI(j, 0, n >> 1) {
            // assign maxes
            int i1 = num_max[j].se;
            int i2 = picked[i1].back();
            int xspace_i2 = xwind[i1][i2].se;
            talloc[i1][xspace_i2] = i;
            picked[i1].pop_back();

            num_max[j].fi--;
        }

        LI(j, n >> 1, n) {
            // assign mins
            int i1 = num_max[j].se;
            int i2 = picked[i1].front();
            int xspace_i2 = xwind[i1][i2].se;
            talloc[i1][xspace_i2] = i;
            picked[i1].pop_front();
        }
    }

    allocate_tickets(talloc);

    return ans;
}

#ifdef DEBUG
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    
    vvi x;

    LI(i, 0, n) {
        vi xr(m, 0);
        vi tar;
        INPV(xr);
        x.pb(xr);
        ta.pb(tar);
    }

    cout << find_maximum(k, x) << "\n";

    LI(i, 0, n) {
        LI(j, 0, m) cout << ta[i][j] << " ";
        cout << "\n";
    }

    return 0;
}
#endif

• 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