Submission #1051717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051717		LittleOrange	Carnival Tickets (IOI20_tickets)	C++17	55 / 100	635 ms	163840 KiB

tickets

#include "tickets.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 1e18;
struct obj{
	ll v,i,j;
	bool operator<(const obj &o) const{
		return v<o.v;
	}
	bool operator>(const obj &o) const{
		return v>o.v;
	}
};
struct pr{
	ll i,c;
	bool operator<(const pr &o) const{
		return c<o.c;
	}
};
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	ll n = x.size();
	ll m = x[0].size();
	vector<vector<int>> ans(n,vector<int>(m,-1));
	/*if (m == 1){
		vector<ll> v;
		for(ll i = 0;i<n;i++) {
			v.push_back(x[i][0]);
			ans[i][0] = 0;
		}
		allocate_tickets(ans);
		sort(v.begin(),v.end());
		ll sm = 0;
		for(ll i : v) sm += abs(i-v[v.size()/2]);
		return sm;
	}*/
	if (k==1){
		vector<deque<pair<ll,ll>>> a(n);
		for(ll i = 0;i<n;i++){
			for(ll j = 0;j<m;j++){
				a[i].push_back({x[i][j],j});
			}
			sort(a[i].begin(),a[i].end());
		}
		ll sm = 0;
		for(ll r = 0;r<k;r++){
			/*for(ll i = 0;i<n;i++){
				cerr << i << ":";
				for(auto [v,j] : a[i]){
					cerr << " " << v << "," << j;
				}
				cerr << "\n";
			}*/
			vector<pair<ll,ll>> ord;
			for(ll i = 0;i<n;i++){
				ord.push_back({a[i].front().first+a[i].back().first,i});
			}
			sort(ord.begin(),ord.end());
			for(ll i = 0;i<n/2;i++){
				auto [v,j] = a[ord[i].second].front();a[ord[i].second].pop_front();
				ans[ord[i].second][j] = r;
				//cerr << r << " -> " << ord[i].second << " " << j << "\n";
				sm -= v;
			}
			for(ll i = n/2;i<n;i++){
				auto [v,j] = a[ord[i].second].back();a[ord[i].second].pop_back();
				ans[ord[i].second][j] = r;
				//cerr << r << " -> " << ord[i].second << " " << j << "\n";
				sm += v;
			}
		}
		allocate_tickets(ans);
		return sm;
	}
	ll sub3 = 1;
	for(auto &o : x) for(ll i : o) if(i>1) sub3 = 0;
	if(sub3){
		ll sm = 0;
		vector<vector<obj>> v0(n),v1(n);
		for(ll i = 0;i<n;i++){
			for(ll j = 0;j<m;j++){
				if(x[i][j])v1[i].push_back({x[i][j],i,j});
				else v0[i].push_back({x[i][j],i,j});
			}
		}
		priority_queue<pr> q0,q1;
		for(ll i = 0;i<n;i++){
			if (v0[i].size()) q0.push({i,(ll)v0[i].size()});
			if (v1[i].size()) q1.push({i,(ll)v1[i].size()});
		}
		for(ll j = 0;j<k;j++){
			vector<pr> wait0,wait1;
			vector<ll> u(n,0);
			ll req = n/2;
			while(req&&q1.size()){
				sm++;
				pr p = q1.top();q1.pop();
				p.c = v1[p.i].size();
				if (!p.c) continue;
				obj o = v1[p.i].back();v1[p.i].pop_back();
				p.c--;
				ans[o.i][o.j] = j;
				u[o.i] = 1;
				if(p.c) wait1.push_back(p);
				req--;
			}
			for(ll i = 0;i<n;i++) if(!u[i]){
				if (v0[i].size()){
					obj o = v0[i].back();v0[i].pop_back();
					ans[o.i][o.j] = j;
				}else{
					sm--;
					obj o = v1[i].back();v1[i].pop_back();
					ans[o.i][o.j] = j;
				}
			}
			for(pr p : wait0) q0.push(p);
			for(pr p : wait1) q1.push(p);
		}
		allocate_tickets(ans);
		return sm;
	}
	if(k==m){
		ll sm = 0;
		vector<obj> a;
		for(ll i = 0;i<n;i++){
			for(ll j = 0;j<m;j++){
				a.push_back({x[i][j],i,j});
			}
		}
		sort(a.begin(),a.end());
		ll nm = n*m;
		vector<vector<ll>> y(n,vector<ll>(m,1));
		for(ll i = 0;i<nm/2;i++){
			sm += a.end()[-i-1].v-a[i].v;
			y[a[i].i][a[i].j] = 0;
		}
		{
			vector<vector<obj>> v0(n),v1(n);
			for(ll i = 0;i<n;i++){
				for(ll j = 0;j<m;j++){
					if(y[i][j])v1[i].push_back({y[i][j],i,j});
					else v0[i].push_back({y[i][j],i,j});
				}
			}
			priority_queue<pr> q0,q1;
			for(ll i = 0;i<n;i++){
				if (v0[i].size()) q0.push({i,(ll)v0[i].size()});
				if (v1[i].size()) q1.push({i,(ll)v1[i].size()});
			}
			for(ll j = 0;j<k;j++){
				vector<pr> wait0,wait1;
				vector<ll> u(n,0);
				ll req = n/2;
				while(req&&q1.size()){
					pr p = q1.top();q1.pop();
					p.c = v1[p.i].size();
					if (!p.c) continue;
					obj o = v1[p.i].back();v1[p.i].pop_back();
					p.c--;
					ans[o.i][o.j] = j;
					u[o.i] = 1;
					if(p.c) wait1.push_back(p);
					req--;
				}
				for(ll i = 0;i<n;i++) if(!u[i]){
					if (v0[i].size()){
						obj o = v0[i].back();v0[i].pop_back();
						ans[o.i][o.j] = j;
					}else{
						obj o = v1[i].back();v1[i].pop_back();
						ans[o.i][o.j] = j;
					}
				}
				for(pr p : wait0) q0.push(p);
				for(pr p : wait1) q1.push(p);
			}
		}
		allocate_tickets(ans);
		return sm;
	}
	ll sm = 0;
	/*vector<obj> v1,v2; // big small
	for(ll i = 0;i<n;i++){
		for(ll j = 0;j<m;j++){
			v1.push_back({x[i][j],i,j});
		}
	}
	sort(v1.begin(),v1.end());
	v2 = v1;
	reverse(v2.begin(),v2.end());
	vector<vector<obj>> g1(n),g2(n);
	ll cnt = n/2*k;
	for(ll i = 0;i<cnt;i++){
		obj o = v1.back();v1.pop_back();
		sm += o.v;
		g1[o.i].push_back(o);
	}
	for(ll i = 0;i<cnt;i++){
		obj o = v2.back();v2.pop_back();
		sm -= o.v;
		g2[o.i].push_back(o);
	}
	ll bad = 0;
	for(ll i = 0;i<n;i++) if((ll)(g1[i].size()+g2[i].size())>k) bad++;
	while(bad){
		obj o1 = {big,-1,-1}, o2 = {-big,-1,-1};
		for(ll i = 0;i<n;i++) if((ll)(g1[i].size()+g2[i].size())>k){
			o1 = min(o1,g1[i].back());
			o2 = max(o2,g2[i].back());
		}
		ll d1 = o1.v-v1.back().v;
		ll d2 = v2.back().v-o2.v;
		if (d1<=d2){
			sm -= d1;
			g1[o1.i].pop_back();
			g1[v1.back().i].push_back(v1.back());
			v1.pop_back();
		}else{
			sm -= d2;
			g2[o2.i].pop_back();
			g2[v2.back().i].push_back(v2.back());
			v2.pop_back();
		}
		bad = 0;
		for(ll i = 0;i<n;i++) if((ll)(g1[i].size()+g2[i].size())>k) bad++;
	}*/
	/*
	vector<pair<ll,ll>> ord;
	for(ll i = 0;i<n;i++) ord.push_back({g1[i].size(),i});
	sort(ord.begin(),ord.end(),greater<pair<ll,ll>>());
	for(ll j = 0;j<k;j++){
		ll c1 = n/2;
		for(auto [_,i] : ord){
			obj x;
			if (g1[i].size()&&c1--){
				x = g1[i].back();g1[i].pop_back();
			}else{
				x = g2[i].back();g2[i].pop_back();
			}
			ans[i][x.j] = j;
		}
	}*/
	{
		vector<obj> a;
		for(ll i = 0;i<n;i++){
			for(ll j = 0;j<m;j++){
				a.push_back({x[i][j],i,j});
			}
		}
		sort(a.begin(),a.end());
		ll nm = n*m;
		vector<vector<ll>> y(n,vector<ll>(m,1));
		for(ll i = 0;i<nm/2;i++){
			y[a[i].i][a[i].j] = 0;
		}
		/*vector<vector<ll>> y(n,vector<ll>(m,-1));
		for(ll i = 0;i<n;i++){
			for(obj o : g1[i]) y[i][o.j] = 1;
			for(obj o : g2[i]) y[i][o.j] = 0;
		}*/
		{
			vector<vector<obj>> v0(n),v1(n);
			for(ll i = 0;i<n;i++){
				for(ll j = 0;j<m;j++){
					if(y[i][j]==1)v1[i].push_back({y[i][j],i,j});
					else if(y[i][j]==0)v0[i].push_back({y[i][j],i,j});
				}
			}
			priority_queue<pr> q0,q1;
			for(ll i = 0;i<n;i++){
				if (v0[i].size()) q0.push({i,(ll)v0[i].size()});
				if (v1[i].size()) q1.push({i,(ll)v1[i].size()});
			}
			for(ll j = 0;j<k;j++){
				vector<pr> wait0,wait1;
				vector<ll> u(n,0);
				ll req = n/2;
				while(req&&q1.size()){
					pr p = q1.top();q1.pop();
					p.c = v1[p.i].size();
					if (!p.c) continue;
					obj o = v1[p.i].back();v1[p.i].pop_back();
					p.c--;
					ans[o.i][o.j] = j;
					u[o.i] = 1;
					if(p.c) wait1.push_back(p);
					req--;
				}
				for(ll i = 0;i<n;i++) if(!u[i]){
					if (v0[i].size()){
						obj o = v0[i].back();v0[i].pop_back();
						ans[o.i][o.j] = j;
					}else{
						obj o = v1[i].back();v1[i].pop_back();
						ans[o.i][o.j] = j;
					}
				}
				for(pr p : wait0) q0.push(p);
				for(pr p : wait1) q1.push(p);
			}
		}
		{
			vector<vector<ll>> v(k);
			for(ll i = 0;i<n;i++) for(ll j = 0;j<m;j++){
				if(ans[i][j]!=-1) v[ans[i][j]].push_back(x[i][j]);
			}
			for(auto &o : v){
				sort(o.begin(),o.end());
				for(ll i = 0;i<n/2;i++){
					sm += o[n-1-i]-o[i];
				}
			}
		}
	}
	allocate_tickets(ans);
	return sm;
}

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