제출 #659021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659021		evenvalue	카니발 티켓 (IOI20_tickets)	C++17	11 / 100	2 ms	852 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 index;

  bool operator<(const ticket &other) const {
    return value < other.value;
  }

  bool operator>(const ticket &other) const {
    return value > other.value;
  }
};

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

  vector<vector<ticket>> tickets(n, vector<ticket>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      tickets[i][j].value = X[i][j];
      tickets[i][j].color = i;
      tickets[i][j].index = j;
    }
  }

  int64 ans = 0;
  max_heap<ticket> suff;
  vector<max_heap<ticket>> get_max(n);
  for (int i = 0; i < n; i++) {
    sort(tickets[i].begin(), tickets[i].end());
    for (int j = 0; j < m; j++) {
      get_max[i].push(tickets[i][j]);
    }
    for (int j = 0; j < k; j++) {
      suff.push(tickets[i][j]);
      ans -= tickets[i][j].value;
    }
  }
  
  vector<vector<int>> allocate(n, vector<int>(m, -1));

  const int kChoose = n * k;
  assert(suff.size() == kChoose);
  for (int assign = 0; suff.size() > kChoose / 2; assign = (assign + 1) % k) {
    const auto x = suff.top();
    suff.pop();
    const auto y = get_max[x.color].top();
    get_max[x.color].pop();

    ans += x.value + y.value;
    allocate[y.color][y.index] = assign;
  }

  assert(suff.size() == kChoose / 2);
  for (int assign = 0; not suff.empty(); assign = (assign + 1) % k) {
    const auto x = suff.top();
    suff.pop();
    allocate[x.color][x.index] = assign;
  }

  allocate_tickets(allocate);
  return ans;
}

컴파일 시 표준 에러 (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:61:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<ticket, std::vector<ticket>, std::less<ticket> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   61 |   assert(suff.size() == kChoose);
      |          ~~~~~~~~~~~~^~~~~~~~~~
tickets.cpp:62:36: warning: comparison of integer expressions of different signedness: 'std::priority_queue<ticket, std::vector<ticket>, std::less<ticket> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |   for (int assign = 0; suff.size() > kChoose / 2; assign = (assign + 1) % k) {
      |                        ~~~~~~~~~~~~^~~~~~~~~~~~~
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:72:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<ticket, std::vector<ticket>, std::less<ticket> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |   assert(suff.size() == kChoose / 2);
      |          ~~~~~~~~~~~~^~~~~~~~~~~~~~

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