Problema Acciones (AC) - IOI-Etapa1-Problemset8

gistfile1.cpp

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <utility>
#define optimize ios_base::sync_with_stdio(0);cin.tie(0);
#define all(v) v.begin(), v.end()
#define first(v, n) v.begin(), v.begin()+n
#define second(v, n) v.begin()+n, v.begin()+(2*n)
#define sz size()
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long int lli;
typedef vector<lli> Vector;
typedef vector<pair<int, lli> > VectorPair;
int N;
lli num;
Vector acciones;
Vector A,B;
VectorPair CA, CB;
lli sumaTotal = 0;
lli diferencia = 9999999999;
map<int, pair<int, int> > coord;

void generarSubsets(Vector&x, VectorPair&y, lli suma, int indice, int limite, int obtenidos, int capturado){
int i,j;
	if(indice>limite){
		return;
	}
	if(capturado){
		y.PB(MP(obtenidos, suma));
	}
	if(obtenidos == limite){
		return;
	}

	generarSubsets(x,y,suma,indice+1, limite, obtenidos, 0);
	generarSubsets(x,y,suma+x[indice], indice+1, limite, obtenidos+1, 1);
}

void subsets(Vector x, Vector&c, VectorPair&y, char op){
int i,j;
	c.clear();
	for(i=0; i<x.sz; ++i){
		c.push_back(x[i]);
	}
	sort(all(c));
	if(op == 'A'){
		generarSubsets(c,y,c[0],1,N/2,1,1);
	}
	else if(op == 'B'){
		generarSubsets(c,y,0,0,N/2,0,0);
	}
	sort(all(y));
}

int lower(VectorPair x, int valor, int inicio, int fin){
	int a,b,m;
	int i,j,aux;
	a = inicio;
	b = fin;
	m = (a+b)/2;
	while(a<b){
		m = (a+b)/2;
		if( (x[m].first+valor) < (N/2) ){
			a = m+1;
		}
		else if( (x[m].first+valor) > (N/2) ){
			b = m-1;
		}
		else if( (x[m].first+valor) == (N/2) ){
			if( (x[m-1].first+valor) == (N/2)  ){
                b = m-1;
			}
			else if( (x[m-1].first+valor) != (N/2) ){
                break;
			}
		}
	}
	if(a<=b){
        return m;
	}else{
        return -1;
	}
}

int upper(VectorPair x, int valor, int inicio, int fin){
    int a = inicio;
    int b = fin;
    int m;
    while(a<b){
        m = (a+b)/2;
        if( (x[m].first+valor) < (N/2) ){
            a = m+1;
        }
        else if( (x[m].first+valor) > (N/2) ){
            b = m-1;
        }
        else if( (x[m].first+valor) == (N/2) ){

            if( (x[m+1].first+valor) == (N/2) ){
                a = m+1;
            }
            else if( (x[m+1].first+valor) != (N/2) ){
                m = m+1;
                break;
            }

        }
    }
    if(a<=b){
        return m;
    } else {
        return -1;
    }
}

int binSearch(VectorPair&B, int valor, int inicio, int fin){
    int j;
    lli sumaA, sumaB;
    lli dif = 0;
    int a = inicio, b = fin;
    int m, mi, mc, md;
    while(a<=b){
        m = (a+b)/2;
        if(a == b){
            sumaA = (sumaTotal-valor-(B[m].second));
            sumaB = (sumaTotal-sumaA);
            mc = abs( sumaA - sumaB );
            if(mc < diferencia){
                diferencia = mc;
            }
            break;
        }
        sumaA = (sumaTotal-valor-(B[m-1].second));
        sumaB = (sumaTotal-sumaA);
        mi = abs( sumaA - sumaB );

        if(mi < diferencia){
            diferencia = mi;
        }

        sumaA = (sumaTotal-valor-(B[m].second));
        sumaB = (sumaTotal-sumaA);
        mc = abs( sumaA - sumaB );

        if(mc < diferencia){
            diferencia = mc;
        }

        sumaA = (sumaTotal-valor-(B[m+1].second));
        sumaB = (sumaTotal-sumaA);
        md = abs( sumaA - sumaB );

        if(md < diferencia){
            diferencia = md;
        }

        if(mi >= mc and mc > md){
            a = m+1;
        }
        else if(mi < mc and mc <= md){
            b = m-1;
        } else {
            if(mc < diferencia){
                diferencia = mc;
            }
            break;
        }

    }
}

void mitm(VectorPair&A, VectorPair&B){
int i,j;
lli sumaA, sumaB;
lli dif = 0;
int b = 0;

	sumaA = sumaTotal-(B[B.sz-1].second);
	sumaB = sumaTotal-sumaA;
	dif =  abs(sumaA - sumaB);

	if(dif<diferencia){
		diferencia = dif;
	}
	for(i=0; i<A.sz; ++i){
		binSearch(B, A[i].second, coord[A[i].first].first, coord[A[i].first].second);
	}
}

int main(){
	optimize
	int i,j;
	scanf("%d",&N);
	for(i=0; i<N; ++i){
		scanf("%lld",&num);
		acciones.push_back(num);
		sumaTotal += num;
	}
	sort(all(acciones));
	subsets(Vector(first(acciones, N/2)), A, CA,'A');
	subsets(Vector(second(acciones, N/2)), B, CB,'B');
	for(i=1; i<N/2; ++i){
        coord[i].first = lower(CB,i,0,CB.sz-1);
        coord[i].second = upper(CB,i,0,CB.sz-1);
	}
	mitm(CA, CB);
	printf("%lld\n",diferencia);
	return 0;
}