Submission #1059227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059227		esomer	Carnival Tickets (IOI20_tickets)	C++17	14 / 100	246 ms	61068 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

long long find_maximum(int k, vector<vector<int>> x) {
	int n = (int)x.size();
	int m = (int)x[0].size();
	vector<vector<int>> ans(n, vector<int>(m, -1));
	vector<pair<int, int>> rng(n, {0, m-1});
	ll res = 0;
	vector<vector<int>> ones(m+1);
	for(int i = 0; i < n; i++){
		int cnt = 0;
		for(int j = 0; j < m; j++){
			if(x[i][j]) cnt++;
		}
		// cout << "i " << i << " cnt " << cnt << "\n";
		ones[cnt].push_back(i);
	}
	for(int r = 0; r < k; r++){
		vector<bool> done(n, false);
		int lft = n/2;
		ll one = 0, zero = 0;
		vector<pair<int, int>> add;
		// cout << "r " << r << " ones:\n";
		// for(int i = m; i >= 1; i--){
		// 	cout << "i " << i << ": ";
		// 	for(int x : ones[i]) cout << x << " ";
		// 	cout << "\n";
		// } 
		for(int i = m; i >= 1 && lft > 0; i--){
			while(lft > 0 && !ones[i].empty()){
				int row = ones[i].back(); ones[i].pop_back();
				add.push_back({row, i-1});
				done[row] = true;
				lft--;
			}
		}
		for(pair<int, int> p : add){
			if(p.second >= 0) ones[p.second].push_back(p.first);
		}
		for(int i = 0; i < n; i++){
			if(done[i]){
				one++;
				ans[i][rng[i].second] = r;
				rng[i].second--;
			}else{
				if(x[i][rng[i].first]) one++;
				else zero++;
				ans[i][rng[i].first] = r;
				rng[i].first++;
			}
		}
		// cout << "r " << r << " zero "<< zero << " one " << one << "\n";
		res += min(zero, one);
	}
	allocate_tickets(ans);
	return res;
}

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