Submission #1016777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016777		0npata	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	768 ms	76200 KiB

tickets

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

using namespace std;

#define vec vector
#define int long long

const int INF = 1e18;

int find_maximum(int32_t k, std::vector<std::vector<int32_t>> x) {
	int n = x.size();
	int m = x[0].size();

	vec<int> sm_cnt(n);
	for(int i = 0; i<n/2; i++) {
		sm_cnt[i] = k;
	}

	auto comp_row_gain = [&](int i) {
		if(sm_cnt[i] == 0) return -INF;

		return (int) (x[i][sm_cnt[i]-1] + x[i][m-(k-sm_cnt[i])-1]);
	};

	auto comp_row_loss = [&](int i) {
		if(sm_cnt[i] == k) return INF;

		return (int) (x[i][sm_cnt[i]] + x[i][m-(k-sm_cnt[i])]);
	};

	set<pair<int, int>> rows_gain;
	set<pair<int, int>> rows_loss;

	vec<vec<int32_t>> alloc_grid(n, vec<int32_t>(m, -1));

	for(int i = 0; i<n; i++) {
		rows_gain.insert({comp_row_gain(i), i});
		rows_loss.insert({comp_row_loss(i), i});
	}

	while(true) {
		assert(rows_gain.size() == n && rows_loss.size() == n);
		auto highest_gain_row = *rows_gain.rbegin();
		auto lowest_loss_row = *rows_loss.begin();

		if(highest_gain_row.first - lowest_loss_row.first <= 0) break;

		int highest_gain_row_ind = highest_gain_row.second;
		int lowest_loss_row_ind = lowest_loss_row.second;

		rows_gain.erase(highest_gain_row);
		rows_loss.erase(lowest_loss_row);
		int cnt1 = rows_gain.erase({comp_row_gain(lowest_loss_row_ind), lowest_loss_row_ind});
		int cnt2 = rows_loss.erase({comp_row_loss(highest_gain_row_ind), highest_gain_row_ind});
		assert(cnt1 == 1 && cnt2 == 1);

		sm_cnt[highest_gain_row_ind]--;
		sm_cnt[lowest_loss_row_ind]++;

		rows_gain.insert({comp_row_gain(highest_gain_row_ind), highest_gain_row_ind});
		rows_loss.insert({comp_row_loss(highest_gain_row_ind), highest_gain_row_ind});
		rows_gain.insert({comp_row_gain(lowest_loss_row_ind), lowest_loss_row_ind});
		rows_loss.insert({comp_row_loss(lowest_loss_row_ind), lowest_loss_row_ind});
	}

	int ans = 0;

	for(int i = 0; i<n; i++) {
		for(int j = 0; j<sm_cnt[i]; j++) ans -= x[i][j];
		for(int j = m-1; j>=m-(k-sm_cnt[i]); j--) ans += x[i][j];
	}

	for(int i = k; i>0; i--) {
		vec<int> row_ind_perm(n);
		iota(row_ind_perm.begin(), row_ind_perm.end(), 0);
		sort(row_ind_perm.begin(), row_ind_perm.end(), [&](int a, int b) { return sm_cnt[a] < sm_cnt[b]; });
		for(int j = 0; j<n/2; j++) {
			int row_ind = row_ind_perm[j];
			int high_ind = m-(i-sm_cnt[row_ind]);
			alloc_grid[row_ind][high_ind] = i-1;
		}
		for(int j = n/2; j<n; j++) {
			int row_ind = row_ind_perm[j];
			int low_ind = sm_cnt[row_ind]-1;
			alloc_grid[row_ind][low_ind] = i-1;

			sm_cnt[row_ind]--;
		}
	}


	allocate_tickets(alloc_grid);

	return ans;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from tickets.cpp:2:
tickets.cpp: In function 'long long int find_maximum(int32_t, std::vector<std::vector<int> >)':
tickets.cpp:43:27: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   43 |   assert(rows_gain.size() == n && rows_loss.size() == n);
      |          ~~~~~~~~~~~~~~~~~^~~~
tickets.cpp:43:52: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   43 |   assert(rows_gain.size() == n && rows_loss.size() == n);
      |                                   ~~~~~~~~~~~~~~~~~^~~~

• 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