Submission #547339

#	Time	Username	Problem	Language	Result	Execution time	Memory
547339		farhan132	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	714 ms	92648 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> ii;

#define pb push_back
#define ff first
#define ss second

const ll N = 1505;

vector < vector < int > > ans;
vector < ii > col[N];
ll L[N] , R[N] , p[N][2];

long long find_maximum(int k, std::vector<std::vector<int>> x) {

	//return 0;

	ll n = x.size();
	ll m = x[0].size();

	ans.resize(n, vector < int >(m, -1));

	for(ll i = 0; i < n; i++){
		for(ll j = 0; j < m; j++){
			col[i].pb({x[i][j], j});
		}
		sort(col[i].begin() , col[i].end()); L[i] = 0, R[i] = m - 1;
	}
	ll F = 0;
	ll c = 0;
	while(k--){
		vector < pair < ll , ii > > v;
		for(ll i = 0; i < n; i++){
			v.pb({col[i][L[i]].ff, {i, 0}});
			v.pb({col[i][R[i]].ff, {i, 1}});
		}
		ll best = -1;
		vector < ll > A(n);
		sort(v.begin(), v.end());
		for(ll mid = 0; mid < (ll)v.size(); mid++){
			ll res = 0, m = v[mid].ff;
			vector < ll > B(n);
			vector < ii > t;
			for(ll i = 0; i <= mid; i++){
				p[v[i].ss.ff][v[i].ss.ss] = 0;
			}
			for(ll i = mid + 1; i < (ll)v.size(); i++){
				p[v[i].ss.ff][v[i].ss.ss] = 1;
			}
			ll need = n/2;
			for(ll i = 0; i < n; i++){
				if(p[i][0] == p[i][1]){
					if(p[i][0] == 0){
						res += m - col[i][L[i]].ff;
						B[i] = 0;
					}else{
						res += col[i][R[i]].ff - m;
						B[i] = 1;
						need--;
					}
				}else{
					B[i] = 0;
					ll k1 = m - col[i][L[i]].ff;
					ll k2 = col[i][R[i]].ff - m;
					res += k1;
					t.pb({k2 - k1, i});
				}
			}
			sort(t.begin(), t.end(), greater <ii>() );
			if(need < 0 || need > t.size()) continue;
			for(ll i = 0; i < need; i++){
				res += t[i].ff;
				B[t[i].ss] = 1;
			}
			ll f = 0;
			for(auto u : B){
				f += (u == 0 ? -1 : 1);
			}
			if(f) continue;
			if(res > best) A = B , best = res;
		}
		F += best;
		//cout << best << '\n';
		for(ll i = 0; i < n; i++){
			if(A[i] == 0){
				ans[i][col[i][L[i]].ss] = c;
				L[i]++;
			}else{
				ans[i][col[i][R[i]].ss] = c;
				R[i]--;
			}
		}
		c++;
	}
	allocate_tickets(ans);
	return F;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:75:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    if(need < 0 || need > t.size()) continue;
      |                   ~~~~~^~~~~~~~~~

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