| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 642033 | ghostwriter | 카니발 티켓 (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
Tran The Bao
CTL - Da Lat
Cay ngay cay dem nhung deo duoc cong nhan
*/
#define matrix vector<vi>
namespace subtask1 {
ll find_maximum(int k, matrix &x) {
ll rs = 0;
vi a;
EACH(i, x) a.pb(i[0]);
sort(all(a));
int med = a[(sz(a) - 1) / 2];
EACH(i, a) rs += abs(i - med);
EACH(i, x)
EACH(j, i)
j = 0;
allocate_tickets(x);
return rs;
}
}
namespace subtask2 {
ll find_maximum(int k, matrix &x) {
int n = sz(x);
int m = sz(x[0]);
ll rs = 0;
FOR(i, 0, n - 1) rs -= x[i][0];
vpi a(n);
FOR(i, 0, n - 1) a[i] = {x[i][m - 1] + x[i][0], i};
sort(all(a), greater<pi>());
FOR(i, 0, n - 1)
FOR(j, 0, m - 1)
x[i][j] = -1;
FOR(i, 0, n / 2 - 1) {
x[a[i].nd][m - 1] = 0;
rs += a[i].st;
}
FOR(i, n / 2, n - 1) x[a[i].nd][0] = 0;
allocate_tickets(x);
return rs;
}
}
matrix getorder(int k, matrix &x) { // 0 = subtract, 1 = add
int n = sz(x);
int m = sz(x[0]);
matrix ans(n, vi(m, 0));
FOR(i, 0, n - 1)
FOR(j, 0, m - 1)
ans[i][j] = -1;
int l = 0;
FOR(i, 0, n - 1) {
vi a, b;
FOR(j, 0, m - 1)
if (x[i][j] == 0) a.pb(j);
else if (x[i][j] == 1) b.pb(j);
EACH(j, a) {
int y = j;
ans[i][y] = l;
l = (l + 1) % k;
}
int l1 = l;
EACH(j, b) {
int y = j;
ans[i][y] = l1;
l1 = (l1 + 1) % k;
}
}
return ans;
}
namespace subtask4 {
struct Ticket {
int a, i, j;
Ticket() {}
Ticket(int a, int i, int j) : a(a), i(i), j(j) {}
};
bool cmp(Ticket &a, Ticket &b) { return a.a < b.a; }
ll find_maximum(int k, matrix &x) {
int n = sz(x);
int m = sz(x[0]);
int cnt = n / 2 * k;
vector<Ticket> a;
FOR(i, 0, n - 1)
FOR(j, 0, m - 1)
a.pb(Ticket(x[i][j], i, j));
sort(all(a), cmp);
ll rs = 0;
EACH(i, a) rs += i.a;
FOR(i, 0, cnt - 1) rs -= 2 * a[i].a;
FOR(i, 0, n - 1)
FOR(j, 0, m - 1)
x[i][j] = -1;
FOR(i, 0, cnt - 1) x[a[i].i][a[i].j] = 0;
FOR(i, cnt, n * m - 1) x[a[i].i][a[i].j] = 1;
allocate_tickets(getorder(k, x));
return rs;
}
}
namespace subtask5 {
const ll oo = 1e18 + 5;
const int N = 85;
const int M = 3205;
int n, m, k, pre[N][M];
ll a[N][N];
ll d[N][M];
void trace(int i, int j, matrix &x) {
if (i < 0) return;
int cnt = pre[i][j];
FOR(z, 0, cnt - 1) x[i][z] = 0;
FOR(z, m - k + cnt, m - 1) x[i][z] = 1;
trace(i - 1, j - cnt, x);
}
ll find_maximum(int k, matrix &x) {
n = sz(x);
m = sz(x[0]);
subtask5::k = k;
int cnt = n / 2 * k;
FOR(i, 0, n - 1) {
FOR(j, m - k, m - 1) a[i][0] += x[i][j];
FOR(j, 1, k) a[i][j] = a[i][j - 1] - x[i][j - 1] - x[i][m - k + j - 1];
}
FOR(i, 0, n - 1)
FOR(j, 0, cnt) {
d[i][j] = -oo;
FOR(z, 0, min(j, k))
if (d[i][j] < a[i][z] + (i > 0? d[i - 1][j - z] : j - z == 0? 0 : -oo)) {
d[i][j] = a[i][z] + (i > 0? d[i - 1][j - z] : j - z == 0? 0 : -oo);
pre[i][j] = z;
}
}
FOR(i, 0, n - 1)
FOR(j, 0, m - 1)
x[i][j] = -1;
trace(n - 1, cnt, x);
allocate_tickets(getorder(k, x));
return d[n - 1][cnt];
}
}
namespace full_solution {
const int N = 1505;
int n, m, k, pos[N];
matrix x;
struct cmp {
bool operator ()(pi &a, pi &b) {
return x[a.st][a.nd] + x[a.st][m - k + a.nd] < x[b.st][b.nd] + x[b.st][m - k + b.nd];
}
};
ll find_maximum(int k, matrix &x) {
::k = k;
::x = x;
n = sz(x);
m = sz(x[0]);
priority_queue<pi, vpi, cmp> pq;
ll rs = 0;
FOR(i, 0, n - 1) {
FOR(j, 0, k - 1) rs -= x[i][j];
pq.push({i, k - 1});
pos[i] = k - 1;
}
int cnt = n / 2 * k;
WHILE(cnt--) {
pi cur = pq.top();
pq.pop();
rs += x[cur.st][cur.nd] + x[cur.st][m - k + cur.nd + 1];
--pos[cur.st];
if (pos[cur.st] >= 0) pq.push({cur.st, pos[cur.st]});
}
FOR(i, 0, n - 1) {
FOR(j, 0, m - 1) x[i][j] = -1;
FOR(j, 0, pos[i]) x[i][j] = 0;
FOR(j, m - k + pos[i] + 1, m - 1) x[i][j] = 1;
}
allocate_tickets(getorder(k, x));
return rs;
}
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = sz(x);
int m = sz(x[0]);
if (m == 1) return subtask1::find_maximum(k, x);
if (k == 1) return subtask2::find_maximum(k, x);
if (k == m) return subtask4::find_maximum(k, x);
if (n <= 80 && m <= 80) return subtask5::find_maximum(k, x);
return full_solution::find_maximum(k, x);
}
/*
2 3 2
0 1 1
0 1 1
*/