Submission #305294

#	Time	Username	Problem	Language	Result	Execution time	Memory
305294		ocarima	Carnival Tickets (IOI20_tickets)	C++14	25 / 100	1141 ms	75640 KiB

tickets

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

using namespace std;

#define vi vector<int>
#define lli long long int
#define plii pair<lli, lli>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repa(i, a, b) for(int i = (a); i >= (b); i--)
#define debugsl(x) cerr << #x << " = " << x << ", "
#define debug(x) debugsl(x) << endl

#define MAX_N 1502
#define cant first
#define bolsa second

lli suma, a, b, num, mediana, offset;
vector<vector<int> > respuesta;
vector<int> mayores[MAX_N], menores[MAX_N], todos;
pii cantidadMayores[MAX_N];

long long find_maximum(int k, vector<vector<int> > x) {
	int n = x.size();
	int m = x[0].size();

	rep(i, 0, n - 1)
        rep(j, 0, m - 1)
            todos.push_back(x[i][j]);
    sort(todos.begin(), todos.end());
    mediana = todos[(n * m >> 1) - 1];
    if (mediana == todos[n * m - 1]) offset = 1;


	rep(i, 0, n - 1){
        vector<int> bolsa(m);
        respuesta.push_back(bolsa);
	    cantidadMayores[i].bolsa = i;
        rep(j, 0, m - 1){
            if (x[i][j] + offset> mediana){
                mayores[i].push_back(j);
                cantidadMayores[i].cant++;
            }
            else menores[i].push_back(j);
        }
	}

	rep(ronda, 0, k - 1){
	    sort(cantidadMayores, cantidadMayores + n); // ORDENA POR CANTIDAD DE UNOS
	    a = (n / 2) - 1;
	    repa(i, n - 1, n / 2){
            b = cantidadMayores[i].bolsa;
            if (mayores[b].size() > 0){
                num = mayores[b].back();
                respuesta[b][num] = ronda;
                suma += x[b][num] - mediana;
                mayores[b].pop_back();
                cantidadMayores[i].cant--;
	        }
	        else{
                a = i;
                break;
	        }
	    }
	    repa(i, a, 0){
	        b = cantidadMayores[i].bolsa;
	        if (menores[b].size() > 0){
                num = menores[b].back();
                respuesta[b][num] = ronda;
                menores[b].pop_back();
                suma += mediana - x[b][num];
	        }
	        else {
	            num = mayores[b].back();
                respuesta[b][b] = ronda;
                mayores[b].pop_back();
                cantidadMayores[i].cant--;
                suma += x[b][num] - mediana;
	        }
	    }
	}

	rep(i, 0, n - 1){
	    while (mayores[i].size() > 0) { respuesta[i][mayores[i].back()] = -1; mayores[i].pop_back(); }
	    while (menores[i].size() > 0) { respuesta[i][menores[i].back()] = -1; menores[i].pop_back(); }
	}

	allocate_tickets(respuesta);
	return suma;
}

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