제출 #336980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336980		zlxFTH	카니발 티켓 (IOI20_tickets)	C++14	100 / 100	1128 ms	88300 KiB

tickets

// IOI2020 D1T2-Connecting Supertrees(supertrees)
// 陈锋
#include "tickets.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
using namespace std;
typedef long long LL;
typedef vector<int> IVec;
typedef pair<LL, LL> LPair;

LL find_maximum(int K, vector<IVec> d) {
  int N = d.size(), M = d[0].size(); // N color ×M tickets
  vector<IVec> O(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(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 prize = 0;
  IVec Plus(N, 0), minus(N, 0), take(N, 0); // Plus[c] => How many '+'s the color c will send
  priority_queue<LPair> Q; // Q: (change to prize by turning a - into a +, color index)
  for (int c = 0; c < N; c++) {
    for (int j = 0; j < K; j++) prize -= dval(c, j); // First incur prize of all L_c
    assert(Plus[c] == 0);
    Q.push(make_pair(dval(c, M - 1 - Plus[c]) + dval(c, K - 1 - Plus[c]), c)); // Queue a possible - → +
  }

  for (int i = 0; i < N * K / 2; i++) { // trade NK/2 '-' with NK/2 '+'s
    LPair it = Q.top(); Q.pop();
    prize += it.first; // L(c) + R(c)
    int c = it.second, &pc = Plus[c]; // If the color hasn’t reached K +, queue another possible +
    if (++pc < K) Q.push(LPair(dval(c, M - pc - 1) + dval(c, K - pc - 1), c));
  }
  while (!Q.empty()) Q.pop(); // clean the Q

  for (int c = 0; c < N; c++) Q.push(LPair(Plus[c], c)); // Q of (# of '-' remaining, color)
  vector<IVec> S(N, IVec(M, -1));
  // minus[c]: # of '-' color c has sent so far, take[c]: Does this c send a '+' in this round
  for (int ki = 0; ki < K; ki++) { // K rounds
    // Pick N/2 colors with the most '+' used
    for (int c = 0; c < N / 2; c++) take[Q.top().second] = 1, Q.pop();
    for (int c = 0; c < N; c++) { // Check if each color sent a - or +, and change S accordingly
      int &p = Plus[c];
      IVec& s = S[c];
      // color c sent a '+', send the smallest '+', Queue c back
      if (take[c]) s[O[c][M - p]] = ki, Q.push(LPair(--p, c)), take[c] = 0;
      else s[O[c][minus[c]++]] = ki; // color c sent a '-', the smallest -
    }
  }

  allocate_tickets(S);
  return prize;
}

• 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