Submission #1024960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024960		TheWilp	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	759 ms	115948 KiB

tickets

#include "tickets.h"
#include <vector>
#include <algorithm>
#include <queue>

using ll = long long;

class name {
public:
	int i;
	int cost;
	bool operator<(const name& other) const{
		return cost < other.cost;
	}
};

class name2{
public:
	int pos;
	int value;
	bool operator<(const name2& other) const {
		return value < other.value;
	}
};

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int N = x.size();
	int M = x[0].size();
	std::vector<std::vector<name2>> s(N,std::vector<name2>(M));
	std::vector<std::vector<int>> ans(N,std::vector<int>(M,-1));
	std::priority_queue<name> g;
	for(int q = 0;q < N;q++) {
		for(int w = 0;w < M;w++) {
			s[q][w].value = x[q][w];
			s[q][w].pos = w;
		}
		std::sort(s[q].begin(),s[q].end());
	}
	int off_set = M - k;
	std::vector<int> group(N,0);
	for(int q = 0;q < N;q++){
		for(int w = 0;w < k;w++) {
			name n;
			n.cost = -x[q][M - 1 - w];
			if(M - 1 - w - off_set >= 0) n.cost += -x[q][M - 1 - w - off_set];
			n.i = q;
			g.push(n);
		}
	}
	for(int q = 0;q < k * N / 2;q++) {
		name e = g.top();
		g.pop();
		group[e.i]++;
	}
	std::vector<std::vector<int>> round(k);
	int r = 0;
	ll res = 0;
	int maxlower = 0;
	int minupper = 2000000000;
	for(int q = 0;q < N;q++) {
		for(int w = 0;w < group[q];w++) {
			round[r].push_back(s[q][w].value);
			maxlower = std::max(maxlower,s[q][w].value);
			//res -= s[q][w].value;
			ans[q][s[q][w].pos] = r;
			r++;
			r%=k;
		}
		int start_pos = r;
		for(int w = 0;w < k - group[q];w++) {
			round[r].push_back(s[q][M - w - 1].value);
			//res += s[q][M - w - 1].value;
			minupper = std::min(minupper,s[q][ M - w - 1].value);
			ans[q][s[q][M - w - 1].pos] = r;
			r++;
			r%=k;
		}
		r = start_pos;
	}
	if(maxlower > minupper) while(true) int* aa = new int[100000000];
	for(int q = 0;q < k;q++) {
		std::sort(round[q].begin(),round[q].end());
		for(int w = 0;w < N / 2;w++) res -= round[q][w];
		for(int w = N / 2;w < N ;w++) res += round[q][w];
	}
	allocate_tickets(ans);
	return res;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:80:43: warning: unused variable 'aa' [-Wunused-variable]
   80 |  if(maxlower > minupper) while(true) int* aa = new int[100000000];
      |                                           ^~

• 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