Submission #799209

#	Time	Username	Problem	Language	Result	Execution time	Memory
799209		QwertyPi	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1459 ms	171392 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

long long report(int n, int m, int k, vector<vector<int>>& x, vector<int>& c){
	vector<vector<int>> ans(n, vector<int>(m, -1));
	vector<pair<int, int>> v;
	for(int i = 0; i < n; i++){
		v.push_back({c[i], i});
	}
	vector<int> l(n, 0), r(n, m - 1);
	long long res = 0;
	for(int i = 0; i < k; i++){
		sort(v.begin(), v.end(), [](pair<int, int> p1, pair<int, int> p2){
			return p1.first > p2.first;
		});
		for(int j = 0; j < n / 2; j++){
			res += x[v[j].second][r[v[j].second]];
			ans[v[j].second][r[v[j].second]--] = i;
			v[j].first--;
		}
		for(int j = n / 2; j < n; j++){
			res -= x[v[j].second][l[v[j].second]];
			ans[v[j].second][l[v[j].second]++] = i;
		}
	}
	allocate_tickets(ans);
	return res;
}

struct value_key{
	long long value, key, id; bool negative;
	bool operator< (const value_key& o) const {
		return value < o.value;
	}
};

struct result_type{
	int left, right;
};

bool used[1500 * 1500];
result_type lambda_maximum(long long lambda, int n, int m, int k, vector<value_key>& a, vector<int>& p, vector<int>& p2){
	int L = 0, R = n * m - 1;
	fill(used, used + n * m, false);
	vector<long long> cnt(n, 0), prev_value(n, -(1LL << 31)), prev_cnt(n, 0);
	fill(p.begin(), p.end(), 0);
	fill(p2.begin(), p2.end(), 0);
	int left_bound = 0, right_bound = 0;
	while(L < n * m || R >= 0){
		long long value; int key, id; bool negative;
		if(R == -1 || (L < n * m && lambda - a[L].value >= a[R].value)){
			value = lambda - a[L].value; key = a[L].key; id = a[L++].id; negative = true;
		}else{
			value = a[R].value; key = a[R].key; id = a[R--].id; negative = false;
		}
		if(used[id]){
			if(value * 2 == lambda){
				if(negative){
					p[key]--; p2[key]++; left_bound--;
				}else{
					p2[key]++; right_bound++;
				}
			}
			continue;
		}
		if(cnt[key] < k){
			used[id] = true;
			cnt[key]++; if(!negative) p[key]++, left_bound++, right_bound++;
			prev_cnt[key] = (prev_value[key] == value ? prev_cnt[key] + (negative) : negative);
			prev_value[key] = value;
		}else if(prev_value[key] == value){
			if(!negative && prev_cnt[key] > 0) prev_cnt[key]--, p2[key]++, right_bound++;
		}
	}
	return {left_bound, right_bound};
}

long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size(), m = x[0].size();
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			x[i][j] <<= 1;
		}
	}
	vector<value_key> a;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			a.push_back({x[i][j], i, i * m + j});
		}
	}
	sort(a.begin(), a.end());
	long long L = 0, R = 1LL << 32;
	vector<int> p(n), p2(n);
	while(L <= R){
		long long M = (L + R) / 2;
		result_type range = lambda_maximum(M, n, m, k, a, p, p2);
		if(range.right < n * k / 2){
			R = M - 1;
		}else if(range.left > n * k / 2){
			L = M + 1;
		}else{
			int cnt = range.left;
			for(int i = 0; i < n; i++){
				while(cnt < n * k / 2 && p2[i] > 0){
					cnt++; p[i]++; p2[i]--;
				}
			}
			long long ans = report(n, m, k, x, p) >> 1;
			return ans;
		}
	}
	return -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