Cod sursa(job #1331903)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 1 februarie 2015 12:31:11
Problema Schi Scor 70
Compilator cpp Status done
Runda tabaraichb Marime 2.04 kb
#include <stdio.h>
#define NMAX 30000
FILE *fin, *fout;
short int n, arb[4*NMAX+23], v[NMAX+23], v2[NMAX+23], poz;
char buff[NMAX];
void citeste(short int &numar)
{
    numar = 0;
    char semn = '+';
    while(buff[poz] > '9' || buff[poz] < '0')
    {
        semn = buff[poz];
        poz++;
        if(poz == NMAX)
        {
            poz = 0;
            fread(buff,1,NMAX,fin);
        }
    }
    while(buff[poz] >= '0' && buff[poz] <= '9')
    {
        numar = numar*10 + buff[poz] - '0';
        poz++;
        if(poz == NMAX)
        {
            poz = 0;
            fread(buff,1,NMAX,fin);
        }
    }
    if(semn == '-')
    {
        numar = -numar;
    }
}
void pun(short int st, short int dr, short int pos, short int nod)
{
    if(st == dr)
    {
        arb[nod] = 1;
        return;
    }
    short int mij = (st+dr)/2;
    if(pos <=  mij) pun(st, mij, pos, 2*nod);
    if(pos > mij) pun(mij+1, dr, pos, 2*nod+1);
    arb[nod] = arb[2*nod] + arb[2*nod+1];
    return;
}
short int interogare(short int st, short int dr, short int st1, short int dr1, short int nod)
{
    if(st == st1 && dr == dr1) return arb[nod];
    short int mij = (st+dr)/2;
    if(st1 > mij) return interogare(mij+1, dr, st1, dr1, 2*nod+1);
    if(dr1 <= mij) return interogare(st, mij, st1, dr1, 2*nod);
    return interogare(st, mij, st1, mij, 2*nod) + interogare(mij+1, dr, mij+1, dr1, 2*nod+1);
}
int main()
{
    fin = fopen("schi.in", "r");
    fout = fopen("schi.out", "w");
    //fread(buff, 1, NMAX, fin);
    //fscanf(fin, "%d", &n);
    citeste(n);
    for(short int i = 0; i< n; i++) citeste(v[i]);
    for(short int i = n-1; i>=0; i--)
    {
        short int temp = v[i], temp1;
        while(1)
        {
            temp1 = temp;
            temp=interogare(1, n, 1, temp, 1) + v[i];
            if(temp == temp1) break;
        }
        pun(1, n, temp, 1);
        v2[temp] = i+1;
    }
    for(int i = 1; i<= n; i++) fprintf(fout, "%d\n", v2[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}