Submission #642036

#	Time	Username	Problem	Language	Result	Execution time	Memory
642036		ghostwriter	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	774 ms	71788 KiB

tickets

#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) {
		full_solution::k = k;
		full_solution::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];
			--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
*/

Compilation message (stderr)

tickets.cpp: In function 'll subtask1::find_maximum(int, std::vector<std::vector<int> >&)':
tickets.cpp:29:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
tickets.cpp:44:3: note: in expansion of macro 'EACH'
   44 |   EACH(i, x) a.pb(i[0]);
      |   ^~~~
tickets.cpp:29:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
tickets.cpp:47:3: note: in expansion of macro 'EACH'
   47 |   EACH(i, a) rs += abs(i - med);
      |   ^~~~
tickets.cpp:29:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
tickets.cpp:48:3: note: in expansion of macro 'EACH'
   48 |   EACH(i, x)
      |   ^~~~
tickets.cpp:29:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
tickets.cpp:49:3: note: in expansion of macro 'EACH'
   49 |   EACH(j, i)
      |   ^~~~
tickets.cpp: In function 'll subtask2::find_maximum(int, std::vector<std::vector<int> >&)':
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:60:3: note: in expansion of macro 'FOR'
   60 |   FOR(i, 0, n - 1) rs -= x[i][0];
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:62:3: note: in expansion of macro 'FOR'
   62 |   FOR(i, 0, n - 1) a[i] = {x[i][m - 1] + x[i][0], i};
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:64:3: note: in expansion of macro 'FOR'
   64 |   FOR(i, 0, n - 1)
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:65:3: note: in expansion of macro 'FOR'
   65 |   FOR(j, 0, m - 1)
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:67:3: note: in expansion of macro 'FOR'
   67 |   FOR(i, 0, n / 2 - 1) {
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:71:3: note: in expansion of macro 'FOR'
   71 |   FOR(i, n / 2, n - 1) x[a[i].nd][0] = 0;
      |   ^~~
tickets.cpp: In function 'std::vector<std::vector<int> > getorder(int, std::vector<std::vector<int> >&)':
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:80:2: note: in expansion of macro 'FOR'
   80 |  FOR(i, 0, n - 1)
      |  ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:81:2: note: in expansion of macro 'FOR'
   81 |  FOR(j, 0, m - 1)
      |  ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:84:2: note: in expansion of macro 'FOR'
   84 |  FOR(i, 0, n - 1) {
      |  ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:86:3: note: in expansion of macro 'FOR'
   86 |   FOR(j, 0, m - 1)
      |   ^~~
tickets.cpp:29:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
tickets.cpp:89:3: note: in expansion of macro 'EACH'
   89 |   EACH(j, a) {
      |   ^~~~
tickets.cpp:29:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
tickets.cpp:95:3: note: in expansion of macro 'EACH'
   95 |   EACH(j, b) {
      |   ^~~~
tickets.cpp: In function 'll subtask4::find_maximum(int, std::vector<std::vector<int> >&)':
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:115:3: note: in expansion of macro 'FOR'
  115 |   FOR(i, 0, n - 1)
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:116:3: note: in expansion of macro 'FOR'
  116 |   FOR(j, 0, m - 1)
      |   ^~~
tickets.cpp:29:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
tickets.cpp:120:3: note: in expansion of macro 'EACH'
  120 |   EACH(i, a) rs += i.a;
      |   ^~~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:121:3: note: in expansion of macro 'FOR'
  121 |   FOR(i, 0, cnt - 1) rs -= 2 * a[i].a;
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:122:3: note: in expansion of macro 'FOR'
  122 |   FOR(i, 0, n - 1)
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:123:3: note: in expansion of macro 'FOR'
  123 |   FOR(j, 0, m - 1)
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:125:3: note: in expansion of macro 'FOR'
  125 |   FOR(i, 0, cnt - 1) x[a[i].i][a[i].j] = 0;
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:126:3: note: in expansion of macro 'FOR'
  126 |   FOR(i, cnt, n * m - 1) x[a[i].i][a[i].j] = 1;
      |   ^~~
tickets.cpp: In function 'void subtask5::trace(int, int, std::vector<std::vector<int> >&)':
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:141:3: note: in expansion of macro 'FOR'
  141 |   FOR(z, 0, cnt - 1) x[i][z] = 0;
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:142:3: note: in expansion of macro 'FOR'
  142 |   FOR(z, m - k + cnt, m - 1) x[i][z] = 1;
      |   ^~~
tickets.cpp: In function 'll subtask5::find_maximum(int, std::vector<std::vector<int> >&)':
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:150:3: note: in expansion of macro 'FOR'
  150 |   FOR(i, 0, n - 1) {
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:151:4: note: in expansion of macro 'FOR'
  151 |    FOR(j, m - k, m - 1) a[i][0] += x[i][j];
      |    ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:152:4: note: in expansion of macro 'FOR'
  152 |    FOR(j, 1, k) a[i][j] = a[i][j - 1] - x[i][j - 1] - x[i][m - k + j - 1];
      |    ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:154:3: note: in expansion of macro 'FOR'
  154 |   FOR(i, 0, n - 1)
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:155:3: note: in expansion of macro 'FOR'
  155 |   FOR(j, 0, cnt) {
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:157:4: note: in expansion of macro 'FOR'
  157 |    FOR(z, 0, min(j, k))
      |    ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:163:3: note: in expansion of macro 'FOR'
  163 |   FOR(i, 0, n - 1)
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:164:3: note: in expansion of macro 'FOR'
  164 |   FOR(j, 0, m - 1)
      |   ^~~
tickets.cpp: In function 'll full_solution::find_maximum(int, std::vector<std::vector<int> >&)':
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:187:3: note: in expansion of macro 'FOR'
  187 |   FOR(i, 0, n - 1) {
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:188:4: note: in expansion of macro 'FOR'
  188 |    FOR(j, 0, k - 1) rs -= x[i][j];
      |    ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:200:3: note: in expansion of macro 'FOR'
  200 |   FOR(i, 0, n - 1) {
      |   ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:201:4: note: in expansion of macro 'FOR'
  201 |    FOR(j, 0, m - 1) x[i][j] = -1;
      |    ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:202:4: note: in expansion of macro 'FOR'
  202 |    FOR(j, 0, pos[i]) x[i][j] = 0;
      |    ^~~
tickets.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
tickets.cpp:203:4: note: in expansion of macro 'FOR'
  203 |    FOR(j, m - k + pos[i] + 1, m - 1) x[i][j] = 1;
      |    ^~~

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10