Submission #301474

#	Time	Username	Problem	Language	Result	Execution time	Memory
301474		mythos	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	3 ms	768 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ar array
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(s) (int) (s).size()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define ff(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define FF(i, a, b) for (int i = (int)(a); i >= (int)(b); --i)
#define trav(a, x) for (auto& (a) : (x))
 
using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

int c, k, s;

int count_lower(vi x, int tar) {
	int l = -1, r = sz(x);
	while (r - l > 1) {
		int m = l + r >> 1;
		if (x[m] < tar) l = m;
		else r = m;
	}
	return r;
}

int cnt;

int get_median(vvi a) {
	int l = -1, r = (int) 2e9, tar = -1, big = 0, small = 0;
	while (r - l > 1) {
		small = big = 0;
		tar = l + (r - l) / 2;
		forn(i, sz(a)) {
			small += count_lower(a[i], tar);
			big += count_lower(a[i], tar + 1);
		}
		if (small > c * k / 2) r = tar;
		else if (big < c * k / 2) l = tar;
		else break;
	}
	cnt = small;
	return tar;
}

i64 find_maximum(int _k, vvi d) {
	k = _k, c = sz(d), s = sz(d[0]);
	vvi sums = vvi(c, vi(k));
	forn(i, c) forn(j, k) sums[i][j] = d[i][j] + d[i][s - k + j];
	int median = get_median(sums);
	i64 ans = 0;
	int minus = 0, plus = c * k - 1;
	vvi ret = vvi(c, vi(s));
	forn(i, c) {
		int j = 0;
		for(; j < k && sums[i][j] < median; j++) {
			ret[i][j] = minus % k;
			minus++;
			ans -= d[i][j];
		}
		for(; j < k && sums[i][j] == median && cnt < c * k / 2; j++) {
			ret[i][j] = minus % k;
			minus++; cnt++;
			ans -= d[i][j];
		}
		ff(l, j, s - k + j - 1) ret[i][l] -= 1;
		ff(l, s - k + j, s - 1) {
			ret[i][j] = plus % k;
			plus--;
			ans += d[i][j];
		}
	}
	allocate_tickets(ret);
	return ans;
}

Compilation message (stderr)

tickets.cpp: In function 'int count_lower(vi, int)':
tickets.cpp:41:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int m = l + r >> 1;
      |           ~~^~~

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