Submission #659176

#	Time	Username	Problem	Language	Result	Execution time	Memory
659176		evenvalue	Carnival Tickets (IOI20_tickets)	C++17	76 / 100	1872 ms	202160 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
 
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
 
using int64 = long long;
using ld = long double;
 
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
 
struct ticket {
  int value;
  int color;
  int group;
 
  bool operator<(const ticket &other) const {
    return value < other.value;
  }
 
  bool operator>(const ticket &other) const {
    return value > other.value;
  }
};
 
struct ticket_pair {
  ticket one;
  ticket two;
  int priority;
  
  int value() const {
    return one.value + two.value;
  }

  bool operator<(const ticket_pair &other) const {
    return (value() == other.value() ? priority < other.priority : value() < other.value());
  }

  bool operator>(const ticket_pair &other) const {
    return (value() == other.value() ? priority < other.priority : value() > other.value());
  }
};

bool validate(vector<vector<int>> s, const int k) {
  const int n = s.size();
  const int m = s[0].size();
 
  for (int i = 0; i < n; i++) {
    sort(s[i].rbegin(), s[i].rend());
    const int minus1 = count(s[i].begin(), s[i].end(), -1);
    assert(minus1 == m - k);
    for (int j = 0; j < k; j++) {
      assert(s[i][j] == k - j - 1);
    }
  }
 
  return true;
}
 
int64 find_maximum(const int k, const vector<vector<int>> X) {
  const int n = (int) X.size();   //number of colours
  const int m = (int) X[0].size();//number of tickets
  const int choose = n * k;       //number of tickets to choose
 
  vector<vector<ticket>> tickets(n, vector<ticket>(m));
  for (int color = 0; color < n; color++) {
    for (int group = 0; group < m; group++) {
      tickets[color][group].value = X[color][group];
      tickets[color][group].color = color;
      tickets[color][group].group = group;
    }
  }
 
  vector<max_heap<ticket>> max_ticket(n);
  for (int color = 0; color < n; color++) {
    for (ticket &t : tickets[color]) {
      max_ticket[color].push(t);
    }
  }
 
  max_heap<ticket_pair> pq;
  for (auto color : tickets) {
    sort(color.begin(), color.end());
    for (int i = 0; i < k; i++) {
      pq.push({color[i], color[m - k + i]});
    }
  }
 
  assert(pq.size() == choose);
 
  vector<vector<ticket>> positive(n);
  while (pq.size() > choose / 2) {
    const ticket t = pq.top().two;
    positive[t.color].push_back(t);
    pq.pop();
  }
 
  vector<vector<ticket>> negative(n);
  while (not pq.empty()) {
    const ticket t = pq.top().one;
    negative[t.color].push_back(t);
    pq.pop();
  }
 
  auto size_sum = [&](const vector<vector<ticket>> &foo) {
    int sum = 0;
    for (const auto &color : foo) {
      sum += color.size();
    }
    return sum;
  };
 
  assert(size_sum(positive) == choose / 2);
  assert(size_sum(negative) == choose / 2);
 
  int64 score = 0;
  vector<vector<int>> s(n, vector<int>(m, -1));
 
  for (int round = 0; round < k; round++) {
    vector<int> color(n);
    iota(color.begin(), color.end(), 0);
 
    auto delta = [&](const int i) {
      return (int)positive[i].size() - (int)negative[i].size();
    };
 
    sort(color.begin(), color.end(), [&](const int i, const int j) {
      return delta(i) > delta(j);
    });
 
    for (int i = 0; i < n; i++) {
      auto &v = (i < n / 2 ? positive : negative);
      const ticket t = v[color[i]].back();
      s[t.color][t.group] = round;
      score += (i < n / 2 ? t.value : -t.value);
      v[color[i]].pop_back();
    }
  }
 
  //  assert(validate(s, k));
 
  allocate_tickets(s);
  return score;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from tickets.cpp:2:
tickets.cpp: In function 'int64 find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:94:20: warning: comparison of integer expressions of different signedness: 'std::priority_queue<ticket_pair, std::vector<ticket_pair, std::allocator<ticket_pair> >, std::less<ticket_pair> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   94 |   assert(pq.size() == choose);
      |          ~~~~~~~~~~^~~~~~~~~
tickets.cpp:97:20: warning: comparison of integer expressions of different signedness: 'std::priority_queue<ticket_pair, std::vector<ticket_pair, std::allocator<ticket_pair> >, std::less<ticket_pair> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |   while (pq.size() > choose / 2) {
      |          ~~~~~~~~~~^~~~~~~~~~~~

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