| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 316510 | nikatamliani | 카니발 티켓 (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
// #include "tickets.h"
using namespace std;
#define ll long long
const ll BIG = 1, SMALL = 2, oo = 1e9 + 10;
ll find_maximum(int k, vector < vector < int > > a) {
int n = a.size(), m = a[0].size();
vector < pair < int, int > > g;
vector < vector < int > > L(n, vector < int >(0)), R(n, vector < int > (0));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
g.push_back({a[i][j], i});
}
}
vector < bool > canTake(g.size(), 1);
sort(g.begin(), g.end());
for(int i = 0; i < k * n / 2; ++i) {
canTake[i] = 0;
L[g[i].second].push_back(i);
}
for(int i = g.size() - 1; i >= g.size() - k * n / 2; --i) {
canTake[i] = 0;
R[g[i].second].push_back(i);
}
for(int i = k * n / 2; i < g.size() - k * n / 2; ++i) {
if(L[g[i].second].size() + R[g[i].second].size() < k) {
canTake[i] = 1;
}
}
int Lptr = 0, Rptr = g.size() - 1;
vector < vector < int > > mark(n, vector < int > (m));
for(int i = 0; i < n; ++i) {
reverse(R[i].begin(), R[i].end());
while(L[i].size() + R[i].size() > k) {
while(Lptr < g.size() && canTake[Lptr] == 0 && L[g[Lptr].second].size() + R[g[Lptr].second].size() >= k) ++Lptr;
while(Rptr >= 0 && canTake[Rptr] == 0 && L[g[Rptr].second].size() + R[g[Rptr].second].size() >= k) --Rptr;
int deleteLeft = oo, deleteRight = oo;
int whL = g[Lptr].second;
if(canTake[Lptr] == 1 && L[i].size() && L[whL].size() + R[whL].size() < k) {
deleteLeft = g[Lptr].first - g[L[i].back()].first;
}
int whR = g[Rptr].second;
if(canTake[Rptr] == 1 && R[i].size() && L[whR].size() + R[whR].size() < k) {
deleteRight = g[R[i].back()].first - g[Rptr].first;
}
if(deleteLeft < deleteRight) {
L[i].pop_back();
L[g[Lptr].second].push_back(Lptr);
canTake[Lptr] = 0;
} else {
R[i].pop_back();
R[g[Rptr].second].push_back(Rptr);
canTake[Rptr] = 0;
}
}
}
vector < vector < int > > pL(n, vector < int > (0)), pR(n, vector < int > (0));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < L[i].size(); ++j) mark[i][j] = SMALL, pL[i].push_back(j);
for(int j = 0; j < R[i].size(); ++j) mark[i][m - j - 1] = BIG, pR[i].push_back(m - j - 1);
}
vector < vector < int > > ans(n, vector < int > (m, -1));
vector < vector < int > > f(n + 1, vector < int > (0));
ll sum = 0;
for(int i = 0; i < k; ++i) {
for(int x = 0; x < n; ++x) {
f[pL[x].size()].push_back(x);
}
int cnt = n / 2;
vector < int > cur(n);
for(int x = n; x >= 1; --x) {
for(int pp : f[x]) {
if(cnt == 0) break;
cur[pp] = 1;
--cnt;
}
}
if(cnt != 0) {
while(true) { int x; }
}
for(int x = 0; x < n; ++x) {
if(cur[x]) {
ans[x][pL[x].back()] = i;
sum -= a[x][pL[x].back()];
pL[x].pop_back();
} else {
ans[x][pR[x].back()] = i;
sum += a[x][pR[x].back()];
pR[x].pop_back();
}
}
for(int x = 0; x <= n; ++x) {
f[x].clear();
}
}
// for(auto x : ans) {
// for(int i : x) cout << i << ' '; cout << '\n';
// }
allocate_tickets(ans);
return sum;
}
// int main() {
// cout << find_maximum(2, {{0, 2, 5}, {1, 1, 3}}) << '\n';
// }