Submission #875837

#	Time	Username	Problem	Language	Result	Execution time	Memory
875837		abczz	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	629 ms	141072 KiB

tickets

#include "tickets.h"
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#define ll long long
 
using namespace std;
 
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	priority_queue<array<ll, 3>> pq;
	vector <array<ll, 3>> X[1500][2];
	vector <array<ll, 3>> tmp;
	ll n = x.size(), m = x[0].size(), f = 0, z, cnt[1500];
	vector <vector<int>> V(n);
	for (int i=0; i<n; ++i) {
		cnt[i] = 0;
		V[i].resize(m);
		for (int j=0; j<m; ++j) V[i][j] = 0;
		for (int j=0; j<k; ++j) {
			f -= x[i][j];
			V[i][j] = -1;
		}
		pq.push({x[i][k-1]+x[i][m-1], i, k-1});
	}
	for (int t=0; t<n*k/2; ++t) {
		auto [w, u, v] = pq.top();
		pq.pop();
		f += w;
		V[u][v] = 0;
		V[u][m-1-(k-1-v)] = 1;
		if (v) {
			--v;
			pq.push({x[u][v]+x[u][m-1-(k-1-v)], u, v});
		}
	}
	for (int i=0; i<n; ++i) {
		z = 0;
		for (int j=0; j<m; ++j) {
			if (!V[i][j]) V[i][j] = -1;
			else if (V[i][j] == -1) {
				--cnt[z];
				X[i][0].push_back({i, j, z++});
			} 
			else {
				++cnt[z];
				X[i][1].push_back({i, j, z++});
			}
			V[i][j] = -1;
		}
	}
	for (int i=0; i<n; ++i) {
		int a = 0, b = 0;
		while (a < X[i][0].size() && b < X[i][1].size()) {
			if (a < X[i][0].size()) {
				if (cnt[X[i][0][a][2]] >= 0) {
					++a;
					continue;
				}
			}
			if (b < X[i][1].size()) {
				if (cnt[X[i][1][b][2]] <= 0) {
					++b;
					continue;
				}
			}
			cnt[X[i][0][a][2]] += 2;
			cnt[X[i][1][b][2]] -= 2;
			swap(X[i][0][a][2], X[i][1][b][2]);
			++a, ++b;
		}
		for (int j=0; j<2; ++j) {
			for (auto [y, x, v] : X[i][j]) {
				V[y][x] = v;
			}
		}
	}
	allocate_tickets(V);
	return f;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:28:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |   auto [w, u, v] = pq.top();
      |        ^
tickets.cpp:55:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   while (a < X[i][0].size() && b < X[i][1].size()) {
      |          ~~^~~~~~~~~~~~~~~~
tickets.cpp:55:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   while (a < X[i][0].size() && b < X[i][1].size()) {
      |                                ~~^~~~~~~~~~~~~~~~
tickets.cpp:56:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    if (a < X[i][0].size()) {
      |        ~~^~~~~~~~~~~~~~~~
tickets.cpp:62:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    if (b < X[i][1].size()) {
      |        ~~^~~~~~~~~~~~~~~~
tickets.cpp:74:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |    for (auto [y, x, v] : X[i][j]) {
      |              ^

• 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