Submission #417247

#	Time	Username	Problem	Language	Result	Execution time	Memory
417247		abdzag	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	3 ms	972 KiB

tickets

#include<bits/stdc++.h>
#include "tickets.h"
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const long long inf = 1e15;

using namespace std;
vector<bool> visited(1e6);
vector<vector<ll>> g;
vector<ll> v;
ll curr = 0;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	vector<ll> v;
	ll n = x.size();
	ll m = x[0].size();
	ll ans = 0;
	std::vector<std::vector<int>> answer(x.size(), vector<int>(x[0].size(), -1));
	set<pair<ll, pair<ll, ll>>> greatest;
	set<pair<ll, pair<ll, ll>>> smallest;
	vector<bool> visited(n);
	rep(i, 0, k) {
		visited.clear();
		v.clear();
		visited.resize(n, 0);
		smallest.clear();
		greatest.clear();
		rep(j, 0, n) {
			rep(z, 0, m) {
				if (x[j][z] != -1) {
					smallest.emplace(x[j][z], make_pair(j, z));
					break;
				}
			}
			rrep(z, m - 1, -1) {
				if (x[j][z] != -1) {
					greatest.emplace(-x[j][z], make_pair(j, z));
					break;
				}
			}
		}
		ll counter = 0;
		trav(a, greatest) {
			x[a.second.first][a.second.second] = -1;
			answer[a.second.first][a.second.second] = i;
			visited[a.second.first] = 1;
			v.push_back(-a.first);
			counter++;
			if (counter == n / 2)break;
		}
		counter = 0;
		trav(a, smallest) {
			if (!visited[a.second.first]) {
				answer[a.second.first][a.second.second] = i;
				x[a.second.first][a.second.second] = -1;
				v.push_back(a.first);
				counter++;
			}
			if (counter == n / 2)break;
		}
		sort(all(v));
		ll b = v[v.size() / 2];
		trav(a, v) {
			ans += abs(a - b);
		}
	}
	allocate_tickets(answer);
	return ans;

}

• 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