Cod sursa(job #826795)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 1 decembrie 2012 11:31:46
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
#include <cstdlib>
#include <cstdio>
#define MAX_SIZE 1 << 16
#define left_son ((nod) << 1)
#define right_son ((nod) << 1) +1
using namespace std;


typedef struct
{
    int value;
    short int pos;
}st;

st tree[MAX_SIZE];



int A;
int B;
int N;
int val;
int *vect;

void read_data()
{
    FILE *input = fopen("schi.in","r");
    fscanf(input,"%d",&N);
    vect = new int[MAX_SIZE];
    for (int i = 1 ; i<=N;i++)
    {
        fscanf(input,"%d",&vect[i]);
    }
    fclose(input);

}


void build_tree(int nod , int left , int right)
{
    if (left == right)
    {
        tree[nod].value = vect[left];
        tree[nod].pos = left;
        vect[left] = 0;
        return;
    }
    int middle = (left + right) >> 1;
    build_tree(left_son , left , middle);
    build_tree(right_son , middle+1 , right);
    if (tree[right_son].value <= tree[left_son].value)
    {
        tree[nod] = tree[right_son];
    }
    else
    {
        tree[nod] = tree[left_son];
    }
}

void update_tree(int nod , int left , int right)
{
    if (A > B) return;
    if (A <=left &&  right <= B)
    {
        tree[nod].value += val;
        vect[nod] += val;
        return;
    }
    int middle = (left + right) >> 1;
    if (A <= middle) update_tree(left_son , left , middle);
    if (middle < B) update_tree(right_son ,middle+1,right);

    if (tree[right_son].value <= tree[left_son].value)
    {
        tree[nod].value  = tree[right_son].value + vect[nod];
        tree[nod].pos = tree[right_son].pos;
    }
    else
    {
        tree[nod].value  = tree[left_son].value + vect[nod];
        tree[nod].pos = tree[left_son].pos;
    }
}

int main()
{

    FILE *output = fopen("schi.out","w");
    read_data();
    build_tree(1,1,N);
    for (int i = 1 ; i<=N;i++)
    {
        fprintf(output,"%d\n",tree[1].pos);
        A = 1;
        B = tree[1].pos-1;
        val = 1;
        update_tree(1,1,N);

        A = tree[1].pos;
        B = tree[1].pos;
        val = MAX_SIZE;

        update_tree(1,1,N);


    }
    fclose(output);

    return 0;
}