Submission #931517

#	Time	Username	Problem	Language	Result	Execution time	Memory
931517		beaboss	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	669 ms	76356 KiB

tickets

// Source: https://oj.uz/problem/view/IOI20_tickets
// 

#include "tickets.h"

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }

bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }

// void allocate_tickets(vector<vi> s) {
// 	// for (auto val: s) {
// 	// 	for (auto j : val) cout << j << ' ';
// 	// 	cout << endl;
// 	// }
// }


ll find_maximum(int k, vector<vector<int> > x) {
	ll n = x.size();
	ll m = x[0].size();
	vi state(n, m - k); // stores range of indices for larger half
	vi start(n, 0);
	ll res = 0;

	priority_queue<pii> q;

	FOR(i, 0, n) {
		FOR(j, m-k, m) res += x[i][j];

		q.push( {-x[i][state[i]] - x[i][start[i]], i});
	}

	FOR(_, 0, k * n / 2) {
		ll cur = q.top().s;
		res += q.top().f;
		q.pop();

		state[cur]++;
		start[cur]++;

		if (state[cur] != m) q.push( {-x[cur][state[cur]] - x[cur][start[cur]], cur});
	}

	vector<vector<int> > final(n, vector<int> (m, -1));

	ll round = 0;

	FOR(i, 0, n) {
		FOR(j, 0, start[i]) {
			final[i][j] = round;
			round= (round + 1) % k;
		}
	}


	FOR(i, 0, n) {
		set<ll> vals;
		FOR(i, 0, k) vals.insert(i);
		for (auto val: final[i]) if (val != -1) vals.erase(val);

		FOR(j, state[i], m) {
			final[i][j] = *vals.begin();
			vals.erase(vals.begin());
		}
	}
	allocate_tickets(final);

	return res;

}




// ll main() {
// 	// ios::sync_with_stdio(false);
// 	// cin.tie(nullptr);

// 	// ll res = find_maximum(2, {{0, 2, 5}, {1, 1, 3}});
// 	// cout << res << endl;

// }

• 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