| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 641752 | ghostwriter | Carnival Tickets (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(matrix x) { // 0 = subtract, 1 = add
int n = sz(x);
int m = sz(x[0]);
matrix ans(sz(x));
FOR(i, 0, n - 1)
FOR(j, 0, m - 1)
ans[i][j] = -1;
int l = 0;
FOR(i, 0, n - 1) {
vpi a, b;
FOR(j, 0, m - 1)
if (x[i][j] == 0) a.pb({i, j});
else b.pb({i, j});
EACH(j, a) {
int x = j.st, y = j.nd;
ans[x][y] = l;
l = (l + 1) % k;
}
int l1 = l + 1;
EACH(j, b) {
int x = j.st, y = j.nd;
ans[x][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(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);
return 1;
}
/*
4 2 1
5 9
1 4
3 6
2 7
*/