Submission #305242

#	Time	Username	Problem	Language	Result	Execution time	Memory
305242		ocarima	Carnival Tickets (IOI20_tickets)	C++14	14 / 100	724 ms	68344 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, totalUnos, totalCeros, a;
vector<vector<int> > respuesta;
vector<int> unos[MAX_N], ceros[MAX_N];
pii cantidadUnos[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){
        vector<int> bolsa(m);
        respuesta.push_back(bolsa);
	    cantidadUnos[i].bolsa = i;
        rep(j, 0, m - 1){
            if (x[i][j] == 1){
                unos[i].push_back(j);
                cantidadUnos[i].cant++;
            }
            else ceros[i].push_back(j);
        }
	}

	rep(ronda, 0, k - 1){
	    sort(cantidadUnos, cantidadUnos + n); // ORDENA POR CANTIDAD DE UNOS
	    a = (n / 2) - 1;
	    totalUnos = totalCeros = 0;
	    repa(i, n - 1, n / 2){

	        if (unos[cantidadUnos[i].bolsa].size() > 0){
                respuesta[cantidadUnos[i].bolsa] [unos[cantidadUnos[i].bolsa].back()] = ronda;
                totalUnos++;
                unos[cantidadUnos[i].bolsa].pop_back();
                cantidadUnos[i].cant--;
	        }
	        else{
                a = i;
                break;
	        }
	    }
	    repa(i, a, 0){
	        if (ceros[cantidadUnos[i].bolsa].size() > 0){
                respuesta[cantidadUnos[i].bolsa][ceros[cantidadUnos[i].bolsa].back()] = ronda;
                ceros[cantidadUnos[i].bolsa].pop_back();
                totalCeros++;
	        }
	        else {
                respuesta[cantidadUnos[i].bolsa][unos[cantidadUnos[i].bolsa].back()] = ronda;
                unos[cantidadUnos[i].bolsa].pop_back();
                cantidadUnos[i].cant--;
                totalUnos++;
	        }
	    }
	    suma += (n - abs(totalUnos - totalCeros)) / 2;
	}

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

	allocate_tickets(respuesta);
	return suma;
}

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