Submission #1226588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226588		HappyCapybara	Carnival Tickets (IOI20_tickets)	C++17	25 / 100	537 ms	75344 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

int n, m, k;
vector<vector<int>> a;
vector<vector<int>> pos, neg;

void done(){
	vector<vector<int>> s(n, vector<int>(m, -1));
	pos.resize(n);
	neg.resize(n);
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++){
			if (a[i][j] == 1) pos[i].push_back(j);
			if (a[i][j] == -1) neg[i].push_back(j);
		}
	}
	for (int j=0; j<k; j++){
		vector<int> v;
		for (int i=0; i<n; i++) v.push_back(i);
		sort(v.begin(), v.end(), [](int a, int b){return pos[a].size() < pos[b].size();});
		for (int i=0; i<n/2; i++){
			s[v[i]][neg[v[i]].back()] = j;
			neg[v[i]].pop_back();
		}
		for (int i=n/2; i<n; i++){
			s[v[i]][pos[v[i]].back()] = j;
			pos[v[i]].pop_back();
		}
	}
	allocate_tickets(s);
}

ll find_maximum(int k, vector<vector<int>> x){
	::k = k;
	n = x.size();
	m = x[0].size();
	a.resize(n, vector<int>(m, 0));
	if (k == m){
		vector<int> at;
		for (int i=0; i<n; i++){
			for (int j=0; j<m; j++) at.push_back(x[i][j]);
		}
		sort(at.begin(), at.end());
		ll mid = at[k*n/2], res = 0;
		int y = k*n/2;
		for (int i=0; i<n; i++){
			for (int j=0; j<m; j++){
				if (x[i][j] >= mid && y){
					a[i][j] = 1;
					y--;
				}
				else a[i][j] = -1;
				res += x[i][j]*a[i][j];
			}
		}
		done();
		return res;
	}
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:63:1: warning: control reaches end of non-void function [-Wreturn-type]
   63 | }
      | ^

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