Cod sursa(job #35250)

Utilizator astronomyAirinei Adrian astronomy Data 21 martie 2007 22:29:16
Problema Schi Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <stdio.h>
#include <string.h>

#define left (nod << 1)
#define right ((nod << 1) | 1)
#define mid ((st+dr) >> 1)
#define MAXN (1 << 16)

int N, Min[MAXN], sum[MAXN], Poz[MAXN];

int a, b, val;

void update(int nod, int st, int dr)
{
    if(a <= st && dr <= b)
	    Min[nod] += val, sum[nod] += val;
    else
	{
	    if(a <= mid) update(left, st, mid);
		if(b > mid) update(right, mid+1, dr);
		if(Min[right] <= Min[left])
		    Min[nod] = Min[right] + sum[nod], Poz[nod] = Poz[right];
        else
		    Min[nod] = Min[left] + sum[nod], Poz[nod] = Poz[left];
    }
}

void build(int nod, int st, int dr)
{
    if(st > dr) return ;
	if(st == dr)
	    Min[nod] = sum[st], Poz[nod] = st;
    else
	{
	    build(left, st, mid), build(right, mid+1, dr);
		if(Min[right] <= Min[left])
		    Min[nod] = Min[right], Poz[nod] = Poz[right];
        else
		    Min[nod] = Min[left], Poz[nod] = Poz[left];
    }
}

void read_and_solve(void)
{
    int i, aux;

	scanf("%d\n", &N);

	for(i = 1; i <= N; i++)
	    scanf("%d\n", &sum[i]);
	
    	build(1, 1, N);

	memset(sum, 0, sizeof(sum));

	for(i = 1; i <= N; i++)
	{
	    aux = Poz[1];
	    printf("%d\n", aux);
		if(Poz[1] > 1) a = 1, b = Poz[1] - 1, val = 1, update(1, 1, N);
		a = b = aux, val = MAXN, update(1, 1, N);
    	}	
}

int main(void)
{
    freopen("schi.in", "rt", stdin);
	freopen("schi.out", "wt", stdout);

	read_and_solve();

    return 0;
}