제출 #826323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
826323		amunduzbaev	카니발 티켓 (IOI20_tickets)	C++17	39 / 100	603 ms	48868 KiB

tickets

#include "tickets.h"

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

#define ar array
typedef long long ll;
//~ #define int ll

/*

4 3 2
0 3 8
1 8 10
1 6 8
6 6 7

*/

ll find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	
	ll ans = -1, M;
	
	vector<int> lor_(n);
	
	auto check = [&](int mid){
		ll res = 0;
		ar<int, 2> all {};
		vector<ar<int, 2>> diff;
		vector<int> lor(n);
		
		for(int i=0;i<n;i++){
			for(int j=0;j<k;j++){
				int l = j + m - k;
				if(x[i][l] < mid){
					res += (mid - x[i][j]);
					lor[i]++; all[0]++;
					continue;
				}
				if(mid < x[i][j]){
					res += (x[i][l] - mid);
					all[1]++;
					continue;
				}
				
				lor[i]++;
				all[0]++;
				res += mid - x[i][j];
				diff.push_back({-(mid - x[i][j]) + (x[i][l] - mid), i});
			}
		}
		
		if(all[1] * 2 > n * k || (all[1] + (int)diff.size()) * 2 < n * k) return;
		sort(diff.begin(), diff.end());
		
		while(all[1] * 2 < n * k){
			int i = diff.back()[1]; //, j = diff.back()[1] % m;
			res += diff.back()[0];
			diff.pop_back();
			lor[i]--;
			all[1]++;
		}
		
		if(all[1] * 2 != n * k) assert(false);
		
		if(res > ans){
			ans = res;
			M = mid;
			lor_ = lor;
		}
	};
	
	auto get = [&](vector<int>& lor){
		vector<vector<int>> ans(n, vector<int>(m, -1));
		vector<vector<int>> used(n, vector<int>(m));
		
		vector<int> l(n), r(n);
		for(int i=0;i<n;i++){
			for(int j=0;j<lor[i];j++) used[i][j] = 1;
			for(int j=m-(k - lor[i]);j<m;j++) used[i][j] = 1;
			
			l[i] = 0, r[i] = m - 1;
		}
		
		//~ for(int i=0;i<n;i++){
			//~ for(int j=0;j<m;j++){
				//~ cout<<used[i][j];
			//~ } 
			//~ cout<<endl;
		//~ }
		
		for(int c=0;c<k;c++){
			ar<int, 2> all {};
			queue<int> q;
			for(int i=0;i<n;i++){
				while(!used[i][l[i]]) l[i]++;
				while(!used[i][r[i]]) r[i]--;
				
				if(r[i] < lor[i]){
					ans[i][l[i]] = c;
					l[i]++; all[0]++;
				} else if(lor[i] <= l[i]){
					ans[i][r[i]] = c;
					r[i]--; all[1]++;
				} else {
					ans[i][l[i]] = c;
					l[i]++, all[0]++;
					q.push(i);
				}
			}
			
			assert(all[1] * 2 <= n);
			
			while(!q.empty() && all[1] * 2 < n){
				int i = q.front(); q.pop();
				all[1]++;
				ans[i][--l[i]] = -1;
				ans[i][r[i]--] = c;
			}
			
			//~ for(int i=0;i<n;i++){
				//~ for(int j=0;j<m;j++){
					//~ cout<<ans[i][j]<<" ";
				//~ } cout<<endl;
			//~ } cout<<endl;

			assert(all[1] * 2 == n);
			//~ while(all[1] * 2 != n);
		}
		
		return ans;
	};
	
	check(0);
	check(1);
	
	if(k == m){
		vector<int> tot;
		for(int i=0;i<n;i++) tot.insert(tot.end(), x[i].begin(), x[i].end());
		
		sort(tot.begin(), tot.end());
		check(tot[n * k / 2]);
		
		allocate_tickets(get(lor_));
		return ans;
	}
	
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<m;j++){
			//~ check(x[i][j]);
		//~ }
	//~ }
	
	//~ cout<<M<<endl;
	//~ for(int i=0;i<n;i++) cout<<lor_[i]<<" ";
	//~ cout<<endl;
	
	allocate_tickets(get(lor_));
	return ans;
	
}

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