Submission #832343

#	Time	Username	Problem	Language	Result	Execution time	Memory
832343		penguinman	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1149 ms	205912 KiB

tickets

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

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	ll N = x.size();
	ll M = x[0].size();
	{
		vector<std::tuple<ll,ll,ll>> data;
		rep(i,0,N){
			rep(j,0,M) data.pb(mtp(x[i][j],i,j));
		}
		sort(all(data));
		ll ans = 0;
		ll mid = N*M/2;
		vii left(N), right(N);
		rep(i,0,N*M){
			ll val, I,J; std::tie(val, I,J) = data[i];
			if(left[I].size() < k) left[I].pb(J);
		}
		per(i,N*M-1,0){
			ll val, I,J; std::tie(val, I,J) = data[i];
			if(right[I].size() < k) right[I].pb(J);
		}

		vii use_left(N), use_right(N);
		ll goal = N*k/2;
		ll current = 0;
		std::priority_queue<pii> que;
		rep(i,0,N){
			reverse(all(right[i]));
			use_left[i] = left[i];
			que.push(mp(x[i][right[i].back()]+x[i][left[i].back()], i));
		}

		/*rep(i,0,N){
			cout << "! " << i << ln;
			for(auto el: left[i]) cout << el << " ";
			cout << ln;
			for(auto el: use_right[i]) cout << el << " ";
			cout << ln;
		}*/

		while(current < goal){
			auto el = que.top(); que.pop();
			ll i = el.second;
			use_left[i].pop_back();
			use_right[i].pb(right[i].back());
			right[i].pop_back();
			current++;
			if(right[i].empty() || use_left[i].empty()) continue;
			que.push(mp(x[i][right[i].back()]+x[i][use_left[i].back()], i));
		}

		vector<vector<int>> allocate(N,vector<int>(M,-1));
		{
			data.clear();
			rep(i,0,N){
				for(auto el: use_left[i]) data.pb(mtp(x[i][el],i,el));
				for(auto el: use_right[i]) data.pb(mtp(x[i][el],i,el));
			}
			sort(all(data));
			ll ans = 0;
			ll mid = N*k/2;
			vii left2(N), right2(N);
			rep(i,0,mid){
				ll val, I,J; std::tie(val, I,J) = data[i];
				left2[I].pb(J);
			}
			rep(i,mid,N*k){
				ll val, I,J; std::tie(val, I,J) = data[i];
				right2[I].pb(J);
			}
			use_left = left2;
			use_right = right2;
		}
		vector<pii> cnt(k);
		rep(i,0,k) cnt[i] = mp(0,i);
		rep(i,0,N){
			sort(all(cnt));
			ll idx = 0;
			for(auto el: use_left[i]){
				allocate[i][el] = cnt[idx].second;
				cnt[idx].first++;
				idx++;
				ans -= x[i][el];
			}
			for(auto el: use_right[i]){
				allocate[i][el] = cnt[idx].second;
				cnt[idx].first--;
				idx++;
				ans += x[i][el];
			}
		}
		allocate_tickets(allocate);
		return ans;
	}
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:37:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |    if(left[I].size() < k) left[I].pb(J);
      |       ~~~~~~~~~~~~~~~^~~
tickets.cpp:41:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |    if(right[I].size() < k) right[I].pb(J);
      |       ~~~~~~~~~~~~~~~~^~~
tickets.cpp:81:7: warning: unused variable 'ans' [-Wunused-variable]
   81 |    ll ans = 0;
      |       ^~~
tickets.cpp:33:6: warning: unused variable 'mid' [-Wunused-variable]
   33 |   ll mid = N*M/2;
      |      ^~~

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