| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 405179 | ly20 | 카니발 티켓 (IOI20_tickets) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1512;
int tb[MAXN][MAXN];
vector <int> v0[MAXN], v1[MAXN];
int id0[MAXN], id1[MAXN];
int n, m;
int resp[MAXN][MAXN];
long long find_maximum(int k, vector<vector<int>> x) {
n = x.size();
m = x[0].size();
long long mx = 0;
vector <vector <int> > answer;
//answer.push_back(temp);
set <pair <int, int> > s0, s1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(x[i][j] == 0) v0[i].push_back(j);
else v1[i].push_back(j);
resp[i][j] = 0;
}
}
for(int i = 0; i < n; i++) {
s0.push_back(make_pair(v0[i].size(), i));
s1.push_back(make_pair(v1[i].size(), -i));
}
long long rs = 0;
for(int i = 0; i < k; i++) {
int qt0, qt1;
int ot = n / 2;
int qta, qtb;
if(s0.size() >= ot && s1.size() >= ot) {
qta = ot; qtb = ot;
}
else if(s0.size() < ot) {
qta = s0.size();
qtb = n - qta;
}
else {
qtb = s1.size();
qta = n - qtb;
}
rs += min(qta, qtb);
vector <pair <int, int> > ida;
for(int j = 0; j < qta; j++) {
pair <int, int> a = (*(--s0.end()));
int ia = a.second;
s0.erase(--s0.end());
a.first--;
resp[ia][v0[ia][id0[ia]]] = i;
id0[ia]++;
if(a.first != 0) ida.push_back(a);
}
for(int j = 0; j < ida.size(); j++) s0.insert(ida[j]);
vector <pair <int, int> > idb;
for(int j = 0; j < qtb; j++) {
pair <int, int> b = (*(--s1.end()));
int ib = b.second;
s1.erase(--s1.end());
b.first--;
resp[ib][v1[ib][id1[ib]]] = i;
id1[ib]++;
if(b.first != 0) idb.push_back(b);
}
for(int j = 0; j < idb.size(); j++) s1.insert(idb[j]);
}
for(int i = 0; i < n; i++) {
vector <int> row;
for(int j = 0; j < m; j++) {
row.push_back(resp[i][j]);
}
answer.push_back(row);
}
allocate_tickets(answer);
return resp;
}