제출 #641758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
641758		ghostwriter	Carnival Tickets (IOI20_tickets)	C++14	41 / 100	830 ms	67408 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 subtask3 {
	ll find_maximum(int k, matrix &x) {
		int n = sz(x);
		int m = sz(x[0]);
		vpi a(n, {0, 0});
		FOR(i, 0, n - 1) {
			int sum = 0;
			FOR(j, 0, m - 1) sum += x[i][j];
			a[i] = {sum, i};
		}
		sort(all(a));
		matrix x1 = x;
		FOR(i, 0, n - 1) x[i] = x1[a[i].nd];
		int cnt = n / 2 * k;
		ll rs = 0;
		FOR(i, 0, n - 1) {
			int pos = -1, cnt1 = k;
			FOR(j, 0, m - 1) {
				if (cnt && cnt1 && x[i][j] == 0) pos = j;
				else if (cnt > k * (n - i)) pos = j;
				else break;
				--cnt;
				--cnt1;
			}
			FOR(j, 0, pos) rs -= x[i][j];
			FOR(j, m - k + pos + 1, m - 1) rs += x[i][j];
			FOR(j, 0, m - 1) x[i][j] = -1;
			FOR(j, 0, pos) x[i][j] = 0;
			FOR(j, m - k + pos + 1, m - 1) x[i][j] = 1;
		}
		x1 = getorder(k, x);
		vi pos(n, 0);
		FOR(i, 0, n - 1) pos[a[i].nd] = i;
		FOR(i, 0, n - 1) x[i] = x1[pos[i]];
		allocate_tickets(x);
		return rs;
	}
}
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);
	bool sub3 = 1;
	FOR(i, 0, n - 1)
	FOR(j, 0, m - 1)
		if (x[i][j] > 1)
			sub3 = 0;
	if (sub3) subtask3::find_maximum(k, x);
	if (k == m)	return subtask4::find_maximum(k, x);
	return 1;
}
/*
2 3 3
0 2 5
1 1 3
*/

컴파일 시 표준 에러 (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 subtask3::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:108:3: note: in expansion of macro 'FOR'
  108 |   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:110:4: note: in expansion of macro 'FOR'
  110 |    FOR(j, 0, m - 1) sum += 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:115:3: note: in expansion of macro 'FOR'
  115 |   FOR(i, 0, n - 1) x[i] = x1[a[i].nd];
      |   ^~~
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:118:3: note: in expansion of macro 'FOR'
  118 |   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:120:4: note: in expansion of macro 'FOR'
  120 |    FOR(j, 0, m - 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:127:4: note: in expansion of macro 'FOR'
  127 |    FOR(j, 0, pos) rs -= 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:128:4: note: in expansion of macro 'FOR'
  128 |    FOR(j, m - k + pos + 1, m - 1) rs += 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:129:4: note: in expansion of macro 'FOR'
  129 |    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:130:4: note: in expansion of macro 'FOR'
  130 |    FOR(j, 0, pos) 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:131:4: note: in expansion of macro 'FOR'
  131 |    FOR(j, m - k + pos + 1, m - 1) x[i][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:135:3: note: in expansion of macro 'FOR'
  135 |   FOR(i, 0, n - 1) pos[a[i].nd] = 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:136:3: note: in expansion of macro 'FOR'
  136 |   FOR(i, 0, n - 1) x[i] = x1[pos[i]];
      |   ^~~
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:153:3: note: in expansion of macro 'FOR'
  153 |   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:154:3: note: in expansion of macro 'FOR'
  154 |   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:158:3: note: in expansion of macro 'EACH'
  158 |   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:159:3: note: in expansion of macro 'FOR'
  159 |   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:160:3: note: in expansion of macro 'FOR'
  160 |   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:161:3: note: in expansion of macro 'FOR'
  161 |   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:163:3: note: in expansion of macro 'FOR'
  163 |   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:164:3: note: in expansion of macro 'FOR'
  164 |   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: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:175:2: note: in expansion of macro 'FOR'
  175 |  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:176:2: note: in expansion of macro 'FOR'
  176 |  FOR(j, 0, m - 1)
      |  ^~~

• 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