# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
659167 | evenvalue | 카니발 티켓 (IOI20_tickets) | C++17 | 1981 ms | 193488 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
bool operator<(const ticket_pair &other) const {
return one.value + two.value < other.one.value + other.two.value;
}
bool operator>(const ticket_pair &other) const {
return one.value + two.value > other.one.value + other.two.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);
}
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();
}
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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |