제출 #1226596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226596		HappyCapybara	카니발 티켓 (IOI20_tickets)	C++17	76 / 100	586 ms	75332 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);
		}
	}
	int bruh = 0;
	for (int i=0; i<n; i++) bruh += pos[i].size()+neg[i].size();
	assert(bruh == k*n);
	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();
		}
	}
	for (int i=0; i<n; i++){
		vector<int> v = s[i];
		sort(v.begin(), v.end());
		for (int j=0; j<m; j++){
			if (j < m-k) assert(v[j] == -1);
			else if (j == 0) assert(v[j] == 0);
			else assert(v[j] == v[j-1]+1);
		}
	}
	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;
	}
	priority_queue<pair<int,int>> pq;
	for (int i=0; i<n; i++){
		for (int j=0; j<k; j++) a[i][j] = -1;
		pq.push({x[i][m-1]+x[i][k-1], i});
	}
	vector<int> rem(n, k);
	for (int i=0; i<k*n/2; i++){
		pair<int,int> next = pq.top();
		pq.pop();
		rem[next.second]--;
		a[next.second][rem[next.second]] = 0;
		a[next.second][m-(k-rem[next.second])] = 1;
		if (rem[next.second]) pq.push({x[next.second][rem[next.second]-1]+x[next.second][m-(k-rem[next.second])-1], next.second});
	}
	done();
	ll res = 0;
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++) res += a[i][j]*x[i][j];
	}
	return res;
}

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