Submission #623002

#	Time	Username	Problem	Language	Result	Execution time	Memory
623002		jophyyjh	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	470 ms	53836 KiB

tickets

/**
 * Another problem from tinjyu's training, though we didn't directly go through the
 * full solution. The "minimum sum of dist. to a point" is classic; we know that
 * point b is the median, i.e. any val in [n-th_num, #(n+1)-th_num]. The obs. here is
 * that the actual val we take is irrelevant. Since n is even, the val would be
 * cancelled out so the prize = #sum_of_the_n_larger_num - #sum_of_the_n_smaller_num.
 * 
 * This means in each round, we maximize #sum_of_n_num - #sum_of_remaining because
 * this naturally finds the larger n numbers to minus the n smaller ones
 * In k=1, we know that if we wanna find a num to be part of the smaller numbers,
 * this num has to be the smallest in its row. Similarly, the largest num in the row
 * shall be picked if it's a "larger" element. With some greedy arguments, the n rows
 * with a larger #min + #max shall pick its maximum, while the remaining rows/colors
 * should pick its minimum.
 * 
 * Similarly, this greedy approach is also valid for other k, which means we can
 * finish this problem~
 * 
 * Time Complexity: O(kn * log(n) + mn)
 * Implementation 1
*/

#include <bits/stdc++.h>
#include "tickets.h"

typedef long long   ll;
typedef std::vector<int>    vec;


struct pair_t {
    ll v;
    int original_pos;
};

ll find_maximum(int k, std::vector<vec> x) {
    int n = x.size(), m = x[0].size();

    vec left(n, 0), right(n, m - 1);
    std::vector<vec> tickets(n, vec(m, -1));
    ll max_sum = 0;
    for (int r = 0; r < k; r++) {
        std::vector<pair_t> vals(n);
        for (int j = 0; j < n; j++) {
            vals[j].v = ll(x[j][left[j]]) + ll(x[j][right[j]]);
            vals[j].original_pos = j;
        }
        std::sort(vals.begin(), vals.end(),
                  [](const pair_t& p1, const pair_t& p2) {
                      return p1.v < p2.v;
                  });
        for (int j = 0; j < n / 2; j++) {
            int p = vals[j].original_pos;
            tickets[p][left[p]] = r, max_sum -= x[p][left[p]];
            left[p]++;
        }
        for (int j = n / 2; j < n; j++) {
            int p = vals[j].original_pos;
            tickets[p][right[p]] = r, max_sum += x[p][right[p]];
            right[p]--;
        }
    }
    allocate_tickets(tickets);
    return max_sum;
}

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