| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 300227 | 2020-09-17T01:50:10 Z | Elegia | 카니발 티켓 (IOI20_tickets) | C++17 | 0 ms | 0 KB |
#include "tickets.h"
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> sgn(n, vector<int>(m));
vector<pair<int, pair<int, int>>> profit;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < k; ++j) {
sgn[i][j] = -1;
profit.emplace_back(x[i][j] + x[i][j + m - k], make_pair(i, j));
}
}
nth_element(profit.begin(), profit.begin() + n * k / 2, profit.end());
for (int i = n * k / 2; i < n * k; ++i) {
int u, v;
tie(u, v) = profit[i].second;
++sgn[u][v];
++sgn[u][v + m - k];
}
vector<queue<int>> pos(n), neg(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (sgn[i][j] > 0) {
pos[i].push(j);
} else if (sgn[i][j] < 0) {
neg[i].push(j);
}
}
}
vector<int> level(n, -1);
vector<vector<int>> answer(n, vector<int>(m, -1));
for (int rep = 0; rep < k; ++rep) {
int val = 0;
for (int i = 0; i < n; ++i) {
if (pos[i].empty()) {
--val;
answer[i][neg[i].front()] = rep;
neg[i].pop();
level[i] = rep;
} else if (neg[i].empty()) {
++val;
answer[i][pos[i].front()] = rep;
pos[i].pop();
level[i] = rep;
}
}
for (int i = 0; i < n; ++i) {
if (level[i] == rep) continue;
if (val < 0) {
++val;
answer[i][pos[i].front()] = rep;
pos[i].pop();
} else {
--val;
answer[i][neg[i].front()] = rep;
neg[i].pop();
}
}
}
allocate_tickets(answer);
return 1;
}