Submission #354308

#	Time	Username	Problem	Language	Result	Execution time	Memory
354308		doowey	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	2017 ms	158820 KiB

tickets

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

using namespace std;

typedef long long ll;
typedef pair<ll,int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = 1510;
priority_queue<pii> low[N];
priority_queue<pii> high[N];
vector<vector<int>> sign;
vector<int> tw[N][2];
vector<vector<int>> sol;

ll find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	ll sum = 0;
	priority_queue<pii> vl;
	sign.resize(n);
	sol.resize(n);
	for(int i = 0 ; i < n; i ++ ){
        sign[i].resize(m);
        sol[i].resize(m,-1);
        for(int j = 0 ; j < k ; j ++ ){
            sum -= x[i][j];
            sign[i][j]=-1;
            low[i].push(mp(x[i][j],j));
        }
        for(int j = 0; j < m ; j ++ ){
            high[i].push(mp(x[i][j],j));
        }
        vl.push(mp(low[i].top().fi + high[i].top().fi, i));
	}
	int it;
	int i1, i2;
	for(int flip = 0; flip < n * k / 2; flip ++ ){
        sum += vl.top().fi;
        it = vl.top().se;
        vl.pop();
        i1 = low[it].top().se;
        i2 = high[it].top().se;
        low[it].pop();
        high[it].pop();
        sign[it][i1]=0;
        sign[it][i2]=+1;
        high[it].push(mp(x[it][i1],i1));
        while(!high[it].empty() && sign[it][high[it].top().se] == +1){
            high[it].pop();
        }
        if(!low[it].empty() && !high[it].empty()){
            vl.push(mp(low[it].top().fi + high[it].top().fi, it));
        }
	}
	for(int i = 0 ; i < n; i ++ ){
        for(int j = 0 ; j < m ; j ++ ){
            if(sign[i][j] == -1){
                tw[i][0].push_back(j);
            }
            else if(sign[i][j] == +1){
                tw[i][1].push_back(j);
            }
        }
	}

	for(int r = 0; r < k ; r ++ ){
        vector<pii> ord;
        for(int i = 0 ; i < n; i ++ ){
            ord.push_back(mp(tw[i][1].size(), i));
        }
        sort(ord.begin(), ord.end());
        for(int i = 0 ; i < ord.size(); i ++ ){
            if(i < ord.size() / 2){
                sol[ord[i].se][tw[ord[i].se][0].back()]=r;
                tw[ord[i].se][0].pop_back();
            }
            else{
                sol[ord[i].se][tw[ord[i].se][1].back()]=r;
                tw[ord[i].se][1].pop_back();
            }
        }
	}
	allocate_tickets(sol);
	return sum;
}

Compilation message (stderr)

tickets.cpp: In function 'll find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int>, std::allocator<std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int i = 0 ; i < ord.size(); i ++ ){
      |                         ~~^~~~~~~~~~~~
tickets.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int>, std::allocator<std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             if(i < ord.size() / 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