Submission #301741

#	Time	Username	Problem	Language	Result	Execution time	Memory
301741		rama_pang	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1151 ms	95188 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

long long find_maximum(int k, vector<vector<int>> x) {
  int n = (int) x.size();
  int m = (int) x[0].size();
  // choose k items for each color
  // choose a total of nk/2 + and nk/2 -
  // maximize the sum of + and -
  long long ans = 0;
  vector<int> negative(n, k);
  vector<int> positive(n, 0);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      ans -= x[i][j];
    }
  }
  priority_queue<pair<int, int>> pq;
  for (int i = 0; i < n; i++) {
    if (negative[i] > 0) {
      pq.emplace(x[i][m - positive[i] - 1] + x[i][negative[i] - 1], i);
    }
  }
  for (int rep = 0; rep < n * k / 2 && !pq.empty(); rep++) {
    int i = pq.top().second;
    ans += pq.top().first;
    pq.pop();
    negative[i]--;
    positive[i]++;
    if (negative[i] > 0) {
      pq.emplace(x[i][m - positive[i] - 1] + x[i][negative[i] - 1], i);
    }
  }
  vector<pair<int, int>> small;
  vector<pair<int, int>> large;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < negative[i]; j++) {
      small.emplace_back(i, j);
    }
    for (int j = 0; j < positive[i]; j++) {
      large.emplace_back(i, m - j - 1);
    }
  }
  
  sort(begin(small), end(small));
  sort(begin(large), end(large));
  vector<vector<pair<int, int>>> rounds(k);
  vector<vector<int>> inround(k, vector<int>(n, 0));
  for (int i = 0; i < n * k / 2; i++) {
    rounds[i % k].emplace_back(small[i]);
    inround[i % k][small[i].first] = 1;
  }
  for (int i = 0, j; i < n * k / 2; i = j + 1) {
    for (j = i; j + 1 < n * k / 2 && large[i].first == large[j + 1].first; j++);
    vector<pair<int, int>> elems;
    for (int e = i; e <= j; e++) {
      elems.emplace_back(large[e]);
    }
    for (int r = 0; r < k; r++) {
      if (inround[r][large[i].first] == 0) {
        inround[r][large[i].first] = 1;
        rounds[r].emplace_back(elems.back());
        elems.pop_back();
      }
    }
  }

  vector<vector<int>> tickets(n, vector<int>(m, -1));
  for (int r = 0; r < k; r++) {
    for (int i = 0; i < n; i++) {
      tickets[rounds[r][i].first][rounds[r][i].second] = r;
    }
  }
  allocate_tickets(tickets);
  return ans;
}

• 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