Submission #559892

#	Time	Username	Problem	Language	Result	Execution time	Memory
559892		AlperenT	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1093 ms	106004 KiB

tickets

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

using namespace std;

struct Item{
	int x, i, j;

	bool operator < (const Item &sc) const{
		return array<int, 3>{x, i, j} < array<int, 3>{sc.x, sc.i, sc.j};
	}
};

long long find_maximum(int k, vector<vector<int>> arr){
	int n = arr.size();
	int m = arr[0].size();

	vector ans(n, vector(m, -1));
	long long ansvalue = 0;

	vector<Item> v; 

	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			ansvalue += arr[i][m - 1 - j];
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			v.push_back({arr[i][j] + arr[i][m - k + j], i, j});
		}
	}

	sort(v.begin(), v.end());

	vector zeros(n, vector<int>()), ones(n, vector<int>());

	for(int i = 0; i < (n * k) / 2; i++){
		ansvalue -= v[i].x;

		zeros[v[i].i].push_back(v[i].j);
	}

	for(int i = (n * k) / 2; i < n * k; i++){
		ones[v[i].i].push_back(m - k + v[i].j);
	}

	for(int i = 0; i < n; i++){
		reverse(zeros[i].begin(), zeros[i].end());
		reverse(ones[i].begin(), ones[i].end());
	}

	for(int i = 0; i < k; i++){
		vector<pair<int, int>> v;

		for(int j = 0; j < n; j++) v.push_back({zeros[j].size(), j});

		sort(v.begin(), v.end(), greater<decltype(v[0])>());

		for(int j = 0; j < n / 2; j++){
			ans[v[j].second][zeros[v[j].second].back()] = i;
			zeros[v[j].second].pop_back();
		}

		for(int j = n / 2; j < n; j++){
			ans[v[j].second][ones[v[j].second].back()] = i;
			ones[v[j].second].pop_back();
		}
	}

	allocate_tickets(ans);
	return ansvalue;
}

• 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