Submission #1187822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187822		hamzabc	Carnival Tickets (IOI20_tickets)	C++20	27 / 100	506 ms	71096 KiB

tickets

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


using namespace std;
#define all(x) x.begin(), x.end()


long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> answer(n, vector<int>(m, -1));
	vector<array<int, 3>> fnd(n * m);
	for (int i = 0; i < n * m; i++){
		fnd[i][0] = x[i / m][i % m];
		fnd[i][1] = i / m;
		fnd[i][2] = i % m;
	}
	if (m > k){
		sort(all(fnd));
		int ort = fnd[n * m / 2][0];
		vector<vector<array<long long, 5>>> colorind(n, vector<array<long long, 5>>(k));
		vector<short> indd(n);
		for (int i = 0; i < n * m; i++){
			if (indd[fnd[i][1]] < k){
				colorind[fnd[i][1]][indd[fnd[i][1]]][0] = ort - fnd[i][0];
				colorind[fnd[i][1]][indd[fnd[i][1]]][1] = fnd[i][2];
				colorind[fnd[i][1]][indd[fnd[i][1]]][3] = fnd[i][0];
				indd[fnd[i][1]]++;
			}
		}
		for (int i = n * m - 1; i > 0; i--){
			if (indd[fnd[i][1]] > 0){
				indd[fnd[i][1]]--;
				colorind[fnd[i][1]][indd[fnd[i][1]]][0] -= fnd[i][0] - ort;
				colorind[fnd[i][1]][indd[fnd[i][1]]][2] = fnd[i][2];
				colorind[fnd[i][1]][indd[fnd[i][1]]][4] = fnd[i][0];
			}
		}
		priority_queue<array<int, 2>> pque;
		for (int i = 0; i < n; i++){
			pque.push({ colorind[i][0][0], i });
		}
		for (int i = 0; i < n * k / 2; i++){
			auto f = pque.top();
			pque.pop();
			indd[f[1]]++;
			if (indd[f[1]] < k){
				pque.push({ colorind[f[1]][indd[f[1]]][0], f[1] });
			}
		}
		fnd.clear();
		for (int i = 0; i < n; i++){
			for (int j = 0; j < indd[i]; j++){
				fnd.push_back({ colorind[i][j][3], i, colorind[i][j][1] });
			}
			for (int j = indd[i]; j < k; j++){
				fnd.push_back({ colorind[i][j][4], i, colorind[i][j][2] });
			}
		}
		colorind.clear();
	}
	sort(all(fnd));
	long long ret = 0;
	for (int i = 0; i < n * k / 2; i++){
		ret -= fnd[i][0];
	}
	for (int i = n * k / 2; i < n * k; i++){
		ret += fnd[i][0];
	}
	priority_queue<array<int, 2>> lft, rgt;
	vector<vector<int>> lftsay(n), rgtsay(n);
	for (int i = 0; i < fnd.size() / 2; i++){
		lftsay[fnd[i][1]].push_back(fnd[i][2]);
	}
	for (int i = fnd.size() / 2; i < fnd.size(); i++){
		rgtsay[fnd[i][1]].push_back(fnd[i][2]);
	}
	for (int i = 0; i < n; i++){
		lft.push({ lftsay[i].size(), i });
	}
	for (int i = 0; i < n; i++){
		rgt.push({ rgtsay[i].size(), i });
	}
	vector<array<int, 2>> usedl, usedr;
	vector<int> used(n);
	int ul, ur;
	for (int t = 0; t < min(m, k); t++){
		fill(all(used), 0);
		ul = 0;
		ur = 0;
		for (int r = 0; r < n; r++){
			while (lft.size() && used[lft.top()[1]]){
				usedl.push_back(lft.top());
				lft.pop();
			}
			while (rgt.size() && used[rgt.top()[1]]){
				usedr.push_back(rgt.top());
				rgt.pop();
			}
			if (ul == n / 2){
				auto f = rgt.top();
				answer[f[1]][rgtsay[f[1]].back()] = t;
				rgtsay[f[1]].pop_back();
				used[f[1]] = 1;
				if (f[0] > 1){
					usedr.push_back({ f[0] - 1, f[1] });
				}
				rgt.pop();
				continue;
			}
			if (ur == n / 2){
				auto f = lft.top();
				answer[f[1]][lftsay[f[1]].back()] = t;
				lftsay[f[1]].pop_back();
				used[f[1]] = 1;
				if (f[0] > 1){
					usedr.push_back({ f[0] - 1, f[1] });
				}
				lft.pop();
				continue;
			}
			if (lft.top()[0] > rgt.top()[0]){
				auto f = lft.top();
				answer[f[1]][lftsay[f[1]].back()] = t;
				lftsay[f[1]].pop_back();
				used[f[1]] = 1;
				if (f[0] > 1){
					usedr.push_back({ f[0] - 1, f[1] });
				}
				lft.pop();
				ul++;
			}else{
				auto f = rgt.top();
				answer[f[1]][rgtsay[f[1]].back()] = t;
				rgtsay[f[1]].pop_back();
				used[f[1]] = 1;
				if (f[0] > 1){
					usedr.push_back({ f[0] - 1, f[1] });
				}
				rgt.pop();
				ur++;
			}
		}
		for (auto u : usedl){
			lft.push(u);
		}
		usedl.clear();
		for (auto u : usedr){
			rgt.push(u);
		}
		usedr.clear();
	}
	allocate_tickets(answer);
	return ret;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:42:34: warning: narrowing conversion of '(&(& colorind.std::vector<std::vector<std::array<long long int, 5> > >::operator[](((std::vector<std::vector<std::array<long long int, 5> > >::size_type)i)))->std::vector<std::array<long long int, 5> >::operator[](0))->std::array<long long int, 5>::operator[](0)' from 'std::array<long long int, 5>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
   42 |                         pque.push({ colorind[i][0][0], i });
      |                         ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
tickets.cpp:49:42: warning: narrowing conversion of '(&(& colorind.std::vector<std::vector<std::array<long long int, 5> > >::operator[](((std::vector<std::vector<std::array<long long int, 5> > >::size_type)f.std::array<int, 2>::operator[](1))))->std::vector<std::array<long long int, 5> >::operator[](((std::vector<std::array<long long int, 5> >::size_type)indd.std::vector<short int>::operator[](((std::vector<short int>::size_type)f.std::array<int, 2>::operator[](1))))))->std::array<long long int, 5>::operator[](0)' from 'std::array<long long int, 5>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
   49 |                                 pque.push({ colorind[f[1]][indd[f[1]]][0], f[1] });
      |                                 ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tickets.cpp:55:46: warning: narrowing conversion of '(&(& colorind.std::vector<std::vector<std::array<long long int, 5> > >::operator[](((std::vector<std::vector<std::array<long long int, 5> > >::size_type)i)))->std::vector<std::array<long long int, 5> >::operator[](((std::vector<std::array<long long int, 5> >::size_type)j)))->std::array<long long int, 5>::operator[](3)' from 'std::array<long long int, 5>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
   55 |                                 fnd.push_back({ colorind[i][j][3], i, colorind[i][j][1] });
      |                                 ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tickets.cpp:55:46: warning: narrowing conversion of '(&(& colorind.std::vector<std::vector<std::array<long long int, 5> > >::operator[](((std::vector<std::vector<std::array<long long int, 5> > >::size_type)i)))->std::vector<std::array<long long int, 5> >::operator[](((std::vector<std::array<long long int, 5> >::size_type)j)))->std::array<long long int, 5>::operator[](1)' from 'std::array<long long int, 5>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
tickets.cpp:58:46: warning: narrowing conversion of '(&(& colorind.std::vector<std::vector<std::array<long long int, 5> > >::operator[](((std::vector<std::vector<std::array<long long int, 5> > >::size_type)i)))->std::vector<std::array<long long int, 5> >::operator[](((std::vector<std::array<long long int, 5> >::size_type)j)))->std::array<long long int, 5>::operator[](4)' from 'std::array<long long int, 5>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
   58 |                                 fnd.push_back({ colorind[i][j][4], i, colorind[i][j][2] });
      |                                 ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tickets.cpp:58:46: warning: narrowing conversion of '(&(& colorind.std::vector<std::vector<std::array<long long int, 5> > >::operator[](((std::vector<std::vector<std::array<long long int, 5> > >::size_type)i)))->std::vector<std::array<long long int, 5> >::operator[](((std::vector<std::array<long long int, 5> >::size_type)j)))->std::array<long long int, 5>::operator[](2)' from 'std::array<long long int, 5>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
tickets.cpp:80:42: warning: narrowing conversion of '(& lftsay.std::vector<std::vector<int> >::operator[](((std::vector<std::vector<int> >::size_type)i)))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   80 |                 lft.push({ lftsay[i].size(), i });
      |                            ~~~~~~~~~~~~~~^~
tickets.cpp:83:42: warning: narrowing conversion of '(& rgtsay.std::vector<std::vector<int> >::operator[](((std::vector<std::vector<int> >::size_type)i)))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   83 |                 rgt.push({ rgtsay[i].size(), i });
      |                            ~~~~~~~~~~~~~~^~

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