Submission #329280

#	Time	Username	Problem	Language	Result	Execution time	Memory
329280		chenwz	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1105 ms	72556 KiB

tickets

#include "tickets.h"
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
typedef vector<int> IVec;
typedef pair<LL, LL> pii;

long long find_maximum(int k, vector<IVec> d) {
  int N = d.size(), M = d[0].size(); // N color ×M tickets
  vector<IVec> o(N); // o.resize(N);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) o[i].push_back(j); // o[N][i]:index of ticket which is ith min from left
    // // Sort each color's tickets by their num
    sort(o[i].begin(), o[i].end(), [&](int a, int b) { return d[i][a] < d[i][b]; });
  }
  auto dval = [&](int c, int i) { return d[c][o[c][i]]; }; // num of ticket of color c which is ith form left

  LL cost = 0;
  IVec Plus(N, 0); // Plus[c] => How many '+'s the color c will send
  priority_queue<pii> gain; // gain: (change to cost by turning a - into a +, color index) TODO: ?
  for (int c = 0; c < N; c++) {
    for (int j = 0; j < k; j++) cost -= dval(c, j); // First incur cost of all -s
    gain.push(make_pair(dval(c, M - 1 - Plus[c]) + dval(c, k - 1 - Plus[c]), c)); // Queue a possible - to +
  }

  for (int i = 0; i < N * k / 2; i++) { // Take ck/2 +s
    pii it = gain.top(); gain.pop();
    cost += it.first;
    int c = it.second; // If the color hasnt reached k +s, queue another possible +
    if (++Plus[c] < k)
      gain.push(pii(dval(c, M - 1 - Plus[c]) + dval(c, k - 1 - Plus[c]), c));
  }
  while (!gain.empty()) gain.pop(); // Empty out the priority queue, will use again later
  for (int i = 0; i < N; i++) gain.push(pii(Plus[i], i)); // gain: (+s remaining, color index)
  // minus_count[color] => How many -s the color has sent so far
  vector<int> minus_count;
  minus_count.resize(N, 0);
  // Prepare answer vector dimensions and fill with -1s
  vector<IVec> answer(N, IVec(M, -1));
  IVec take(N, 0); // take[color] => Does this color send a + in this days
  for (int i = 0; i < k; i++) { // Simulate k days of tickets
    for (int j = 0; j < N / 2; j ++) // Pick N/2 companies with the most +s left
      take[gain.top().second] = 1, gain.pop();
    // Check if each color sent a - or +, and change answer accordingly
    for (int j = 0; j < N; j++) {
      if (take[j]) {
        // Company j sent a + this round, send the smallest +
        // Queue the color back
        answer[j][o[j][M - Plus[j]]] = i;
        Plus[j]--;
        gain.push(pii(Plus[j], j));
      } else {
        // Company j sent a - this round, send the smallest -
        answer[j][o[j][minus_count[j]]] = i;
        minus_count[j]++;
      }
      take[j] = 0;
    }
  }

  // Return to grader
  allocate_tickets(answer);
  return cost;
}

• 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