Submission #826290

#	Time	Username	Problem	Language	Result	Execution time	Memory
826290		amunduzbaev	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	3040 ms	17980 KiB

tickets

#include "tickets.h"

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

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

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 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(x[i][r[i]] < M){
					ans[i][l[i]] = c;
					l[i]++; all[0]++;
				} else if(M < x[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;
			}
			
			//~ assert(all[1] * 2 == n);
			//~ while(all[1] * 2 != n);
		}
		
		return ans;
	};
	
	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;
	
	//~ vector<int> l(n), r(n, m - 1);
	
	//~ vector<int> lor_;
	
	//~ 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++){
			//~ if(x[i][r[i]] < mid || mid < x[i][l[i]]){
				//~ if(mid < x[i][l[i]]) all[1]++, res += x[i][r[i]] - mid, lor[i] = 1;
				//~ else all[0]++, res += mid - x[i][l[i]];
				//~ continue;
			//~ }
			
			//~ all[0]++;
			//~ res += mid - x[i][l[i]];
			//~ diff.push_back({(x[i][r[i]] - mid) - (mid - x[i][l[i]]), i});
		//~ }
		
		//~ if(all[1] * 2 > n || (all[1] + (int)diff.size()) * 2 < n) return;
		//~ sort(diff.begin(), diff.end());
		
		//~ while(all[1] * 2 < n){
			//~ all[0]--;
			//~ all[1]++;
			//~ res += diff.back()[0];
			//~ lor[diff.back()[1]] = 1;
			//~ diff.pop_back();
		//~ }
		
		//~ if(ans < res){
			//~ ans = res;
			//~ lor_ = lor;
		//~ }
	//~ };
	
	//~ ll tot = 0;
	
	//~ vector<vector<int>> res(n, vector<int>(m, -1));
	//~ for(int c=0;c<k;c++){
		//~ ans = -1;
		//~ for(int i=0;i<n;i++){
			//~ check(x[i][l[i]]);
			//~ check(x[i][r[i]]);
		//~ }
		
		//~ tot += ans;
		//~ for(int i=0;i<n;i++){
			//~ if(lor_[i]) res[i][r[i]] = c, r[i]--;
			//~ else res[i][l[i]] = c, l[i]++;
		//~ }
	//~ }
	
	//~ allocate_tickets(res);
	//~ return tot;
}

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