Submission #803048

#	Time	Username	Problem	Language	Result	Execution time	Memory
803048		APROHACK	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	386 ms	71288 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
int n, m, K;
vector<int>first, last;
vector<std::vector<int>> answer;
vector<deque<ll>>X;
void use(int color, bool fst, int round){
	if(fst){
		answer[color][first[color]] = round;
		first[color] ++;
		X[color].pop_back();
	}else{
		answer[color][last[color]] = round;
		last[color] --;
		X[color].pop_front();
	}
}



 
long long find_maximum(int k, std::vector< std::vector<int> > x) {
	n = x.size();
	m = x[0].size();
	K = k;
	
	vector<int>row;
	for(int i = 0 ; i < n ; i ++){
		first.pb(0);
		last.pb(m-1);
	}
	for(int i = 0 ; i < m ; i ++)row.pb(-1);
	for(int i  = 0 ; i < n ; i ++)answer.pb(row);
	ll ans = 0;
	if(m == 1){
		for(int r = 0 ; r < k ; r ++){
			vector<ll>acum;
			for(int i = 0 ; i < n ; i ++){
				answer[i][r] = r;
				acum.pb(x[i][r]);
			}
			sort(acum.begin(), acum.end());
			
			for(int i = 0, j = n-1;  i < j; i ++, j--){
				ans += acum[j] - acum[i];
			}
		}
		allocate_tickets(answer);
		return ans;
	}else if(m == k){
		for(int i = 0 ; i < n ; i ++){
			deque<ll>cur;
			for(int j = 0 ; j < m ; j ++)cur.push_front(x[i][j]);
			X.pb(cur);
		}
		for(int r = 0 ; r < k ; r ++){
			ll ans1 = 0, ans2 = 0;
			vector<pair<pair<ll, ll>, ll > > options, options2;
			for(int i = 0 ; i < n ; i ++){
				options.pb({{X[i].back(), X[i].front()}, i});
				options2.pb({{-X[i].front(), -X[i].back()}, i});
			}
			sort(options.begin(), options.end());
			sort(options2.begin(), options2.end());
			for(int i = 0 ; i < n/2 ; i ++){
				ans1 += abs(options[i].ff.ff - options[i + (n/2)].ff.ss);
				//use(options[i].ss, true, r);
				//use(options[i + (n/2)].ss, false, r);
				options2[i].ff.ff *= -1;
				options2[i+(n/2)].ff.ss *= -1;
				ans2 += abs(options2[i].ff.ff - options2[i + (n/2)].ff.ss);
			}
			
			if(ans1 > ans2){
				for(int i = 0 ; i < n/2 ; i ++){
					use(options[i].ss, true, r);
					use(options[i + (n/2)].ss, false, r);
				}
			}else{
				for(int i = 0 ; i < n/2 ; i ++){
					use(options2[i].ss, false, r);
					use(options2[i + (n/2)].ss, true, r);
				}
			}
			ans += max(ans1, ans2);
		}
		allocate_tickets(answer);
		return ans;
	}
	
	
	for(int i = 0 ; i < n ; i ++){
		deque<ll>cur;
		for(int j = 0 ; j < m ; j ++)cur.push_front(x[i][j]);
		X.pb(cur);
	}
	
	for(int r = 0 ; r < k ; r ++){
		vector<ll>acum;
		vector<int>v00, v01, v11;
		for(int i = 0 ; i < n ; i ++){
			if(X[i].back() == 0 and X[i].front() == 0)v00.pb(i);
			else if(X[i].back() == 0 and X[i].front() == 1)v01.pb(i);
			else v11.pb(i);
		}
		//cout << "initially 00 = " << v00.size() << " 11 = " << v11.size() << " 01 = " << v01.size() << endl;
		int cuenta = min(v00.size(), v11.size());
		ans += cuenta;
		for(int i = 0 ; i < cuenta ; i ++){
			use(v00.back(), true, r);
			use(v11.back(), false, r);
			v00.pop_back();
			v11.pop_back();
		}
		cuenta = min(max((int)v00.size(), (int)v11.size()), (int)v01.size());
		ans += cuenta;
		if(v00.size() > v11.size()){
			for(int i = 0 ; i < cuenta ; i ++){
				use(v00.back(), true, r);
				use(v01.back(), false, r);
				v00.pop_back();
				v01.pop_back();
			}
		}else if(v00.size() < v11.size()){
			for(int i = 0 ; i < cuenta ; i ++){
				use(v11.back(), true, r);
				use(v01.back(), true, r);
				v11.pop_back();
				v01.pop_back();
			}
		}
		if(v00.size() == 0 and v11.size() == 0 and v01.size() > 0){
			cuenta = v01.size();
			ans += cuenta/2;
			for(int i = 0 ; i < cuenta ; i += 2){
				use(v01.back(), true, r);
				v01.pop_back();
				use(v01.back(), false, r);
				v01.pop_back();
			}
		}else if(v00.size() > 0){
			cuenta = v00.size();
			for(int i = 0 ; i < cuenta ; i ++){
				use(v00.back(), true, r);
				v00.pop_back();
			}
		}else if(v11.size() > 0 ){
			cuenta = v11.size();
			for(int i = 0 ; i < cuenta ; i ++){
				use(v11.back(), true, r);
				v11.pop_back();
			}
		}
	}
	allocate_tickets(answer);
	return ans;
}

• 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