Submission #600259

#	Time	Username	Problem	Language	Result	Execution time	Memory
600259		definitelynotmee	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	1 ms	212 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix= vector<vector<T>>;

struct ticket{
	int val, id, col;
	ticket();
	ticket(int a, int b, int c){
		val = a, id = b, col = c;
	}
	bool operator<(ticket b) const{
		return make_tuple(val,id,col) < make_tuple(b.val,b.id,b.col);
	}
};

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	matrix<int> resp(n,vector<int>(m,-1));
	for(int i = 0; i < n; i++){
		iota(resp[i].begin(),resp[i].begin()+k,0);
	}
	set<ticket> minus, plus;
	ll ans = 0;
	ll bestans = 0;

	for(int i = 0; i < n/2; i++){
		for(int j = 0; j < k; j++){
			minus.insert({-x[i][j],i,j});
			ans-=x[i][j];
		}
	}
	for(int i = n/2; i < n; i++){
		for(int j = 0; j < k; j++){
			plus.insert({x[i][j],i,j});
			ans+=x[i][j];
		}
	}
	vector<int> o(n);
	iota(all(o),0);
	sort(all(o),[&](int a, int b){
		return resp[a][m-1] > resp[b][m-1];
	});
	while(minus.begin()->val*-1 > plus.begin()->val){
		ticket t1 = *minus.begin(), t2 = *plus.begin();
		minus.erase(minus.begin());
		plus.erase(plus.begin());
		swap(resp[t1.id][t1.col],resp[t2.id][t2.col]);
		ans+=t1.val*-2;
		ans+=t2.val*-2;
		t1.val*=-1;
		t2.val*=-1;
		plus.insert(t1);
		minus.insert(t2);
	}
	bestans = ans;
	for(int i : o){
		if(minus.count(ticket(x[i][0],i,0))){
			ans+=x[i][0];
			minus.erase(ticket(x[i][0],i,0));
			ans-=x[i][m-1];
			swap(resp[i][0],resp[i][m-1]);
			minus.insert(ticket(x[i][m-1],i,m-1));
		} else {
			ans-=x[i][0];
			plus.erase(ticket(x[i][0],i,0));
			ans+=x[i][m-1];
			swap(resp[i][0],resp[i][m-1]);
			plus.insert(ticket(x[i][m-1],i,m-1));
		}
		while(minus.begin()->val*-1 > plus.begin()->val){
			ticket t1 = *minus.begin(), t2 = *plus.begin();
			minus.erase(minus.begin());
			plus.erase(plus.begin());
			swap(resp[t1.id][t1.col],resp[t2.id][t2.col]);
			ans+=t1.val*-2;
			ans+=t2.val*-2;
			t1.val*=-1;
			t2.val*=-1;
			plus.insert(t1);
			minus.insert(t2);
		}
		bestans = max(ans,bestans);
	}
	//cout << "->" << bestans<< '\n';
	{
		minus.clear();
		plus.clear();
		for(int i = 0; i < n; i++){
			iota(resp[i].begin(),resp[i].begin()+k,0);
		}
		ans = 0;
		for(int i = 0; i < n/2; i++){
			for(int j = 0; j < k; j++){
				minus.insert({-x[i][j],i,j});
				ans-=x[i][j];
			}
		}
		for(int i = n/2; i < n; i++){
			for(int j = 0; j < k; j++){
				plus.insert({x[i][j],i,j});
				ans+=x[i][j];
			}
		}
		vector<int> o(n);
		iota(all(o),0);
		sort(all(o),[&](int a, int b){
			return resp[a][m-1] > resp[b][m-1];
		});
		while(minus.begin()->val*-1 > plus.begin()->val){
			ticket t1 = *minus.begin(), t2 = *plus.begin();
			minus.erase(minus.begin());
			plus.erase(plus.begin());
			swap(resp[t1.id][t1.col],resp[t2.id][t2.col]);
			ans+=t1.val*-2;
			ans+=t2.val*-2;
			t1.val*=-1;
			t2.val*=-1;
			plus.insert(t1);
			minus.insert(t2);
		}
		if(ans == bestans){
			allocate_tickets(resp);
		}
		return ans;
		for(int i : o){
			//cout << ans << '\n';
			if(minus.count(ticket(x[i][0],i,0))){
				ans+=x[i][0];
				minus.erase(ticket(x[i][0],i,0));
				ans-=x[i][m-1];
				swap(resp[i][0],resp[i][m-1]);
				minus.insert(ticket(x[i][m-1],i,m-1));
			} else {
				ans-=x[i][0];
				plus.erase(ticket(x[i][0],i,0));
				ans+=x[i][m-1];
				swap(resp[i][0],resp[i][m-1]);
				plus.insert(ticket(x[i][m-1],i,m-1));
			}
			while(minus.begin()->val*-1 > plus.begin()->val){
				ticket t1 = *minus.begin(), t2 = *plus.begin();
				minus.erase(minus.begin());
				plus.erase(plus.begin());
				swap(resp[t1.id][t1.col],resp[t2.id][t2.col]);
				ans+=t1.val*-2;
				ans+=t2.val*-2;
				t1.val*=-1;
				t2.val*=-1;
				plus.insert(t1);
				minus.insert(t2);
			}
			//cout << ans << '\n';
			if(ans == bestans){
				allocate_tickets(resp);
			}
			return ans;
		}
	}
	allocate_tickets(resp);
	return ans;
}

• Subtask 1: 0 / 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