Submission #614104

#	Time	Username	Problem	Language	Result	Execution time	Memory
614104		Tigryonochekk	Carnival Tickets (IOI20_tickets)	C++17	25 / 100	770 ms	107272 KiB

tickets

#include <iostream>
#include <algorithm>
#include "tickets.h"
#include <vector>
#define ll long long
using namespace std;
const ll inf = 1e18 + 69;
#define pii pair<ll, int>
const int N = 1502;

int n, m, k;
vector<vector<int>> x;
vector<vector<int>> answer;
ll ans;
vector<pii> all;
pii cnt[N]; //.first = cnt, .second = index
int sig[N][N]; // +, =, -
int topi[N], boti[N];

pii con(int i, int j) {
	return pii(x[i][j], i * m + j);
}

void play(int j) {
	sort(cnt, cnt + n);
	for (int i = 0; i < n / 2; i++) {
		int ii = cnt[i].second, jj = boti[ii];
		answer[ii][jj] = j;
		boti[ii]++;
	}
	for (int i = n / 2; i < n; i++) {
		int ii = cnt[i].second, jj = topi[ii];
		answer[ii][jj] = j;
		topi[ii]--;
		cnt[i].first--;
	}
}

long long find_maximum(int klir, vector<vector<int>> xuy) {
	k = klir;
	x = xuy;
	n = x.size();
	m = x[0].size();
	answer.resize(n);
	for (int i = 0; i < n; i++) {
		answer[i].resize(m, -1);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			all.push_back(con(i, j));
		}
	}
	sort(all.begin(), all.end());

	pii mid = all[n * m / 2];
	for (int i = 0; i < n; i++) {
		cnt[i] = pii(0, i);
		for (int j = 0; j < m; j++) {
			if (con(i, j) >= mid) {
				sig[i][j] = 1;
				cnt[i].first++;
			}
			else {
				sig[i][j] = -1;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			ans += x[i][j] * sig[i][j];
		}
	}

	fill(topi, topi + n, m - 1);
	fill(boti, boti + n, 0);
	for (int j = 0; j < k; j++) {
		play(j);
	}
	
	allocate_tickets(answer);
	return ans;
}

/*
6 4 4 
1 3 6 7 
2 2 3 5 
5 6 7 8 
1 8 8 9 
3 4 6 7 
2 3 3 3 

2 2 2 
1 4 
2 3 

2 2 2 
1 3 
2 4  

2 2 2 
1 2 
3 4 

2 2 2 
69 69 
69 69 
*/

• 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