Submission #641755

#	Time	Username	Problem	Language	Result	Execution time	Memory
641755		ghostwriter	Carnival Tickets (IOI20_tickets)	C++14	41 / 100	826 ms	86604 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 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;
	}
}
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;
}
/*
2 3 3
0 2 5
1 1 3
*/

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 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:132:6: warning: unused variable 'n' [-Wunused-variable]
  132 |  int n = sz(x);
      |      ^

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