Cod sursa(job #2034294)

Utilizator Coroian_DavidCoroian David Coroian_David Data 7 octombrie 2017 18:02:35
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.22 kb
#include <bits/stdc++.h>

#define MAX_N 30000
#define MAX_BUFF 4096

using namespace std;

FILE *f, *g;

int crChar = MAX_BUFF;

const int buffSize = MAX_BUFF;

char buff[MAX_BUFF + 1];

bool isDigit(char c)
{
    if(c >= '0' && c <= '9')
        return 1;

    return 0;
}

void refillBuff()
{
    crChar = 0;

    fread(buff, 1, buffSize, f);
}

char getCr()
{
    if(crChar == buffSize)
        refillBuff();

    return buff[crChar ++];
}

int getNr()
{
    char c = getCr();
    int nr = 0, sign = 1;

    while(isDigit(c) == 0 && c != '-')
        c = getCr();

    while(c == '-')
    {
        sign = -1;

        c = getCr();
    }

    while(isDigit(c) == 1)
    {
        nr = nr * 10 + c - '0';

        c = getCr();
    }

    return nr * sign;
}

int n;

int v[MAX_N + 1];
int sum[4 * MAX_N + 1];

int loc[MAX_N + 1];

void readFile()
{
    //printf("CITIRE\n");

    f = fopen("schi.in", "r");

    n = getNr();

    int i;
    for(i = 1; i <= n; i ++)
    {
        v[i] = getNr();
    }
    fclose(f);
}

int a, b;

void baga(int poz, int st, int dr)
{
    if(st == dr)
    {
        sum[poz] = b;

        return;
    }

    int mid = (st + dr) / 2;

    if(a >= st && a <= mid)
        baga(poz * 2, st, mid);

    else
        if(a > mid && a <= dr)
            baga(poz * 2 + 1, mid + 1, dr);

    sum[poz] = sum[poz * 2] + sum[poz * 2 + 1];
}

int getSum(int poz, int st, int dr, int a, int b)
{
    //printf("CAUTA SUMA %d %d %d %d %d\n", poz, st, dr, a, b);

    if(st == dr)
        return sum[poz];

    if(st == a && dr == b)
        return sum[poz];

    int mid = (st + dr) / 2;

    if(b <= mid)
        return getSum(poz * 2, st, mid, a, b);

    if(b > mid)
    {
        if(a > mid)
            return getSum(poz * 2 + 1, mid + 1, dr, a, b);

        else
            return getSum(poz * 2, st, mid, a, mid) + getSum(poz * 2 + 1, mid + 1, dr, mid + 1, b);
    }

    return 0;
}

int sum1;

int cautArb(int poz, int st, int dr, int nr)
{
    //printf("SUNTEM PE %d %d %d\n", st, dr, nr);

    if(st == dr)
        return st;

    int mid = (st + dr) / 2;

    if(mid > nr)
    {
    //    printf("SUM %d  %d\n", sum1 + sum[poz * 2], nr - )

        if(sum1 + sum[poz * 2] > mid - nr)
        {
            sum1 += sum[poz * 2];
            return cautArb(poz * 2 + 1, mid + 1, dr, nr);
        }

        else
            return cautArb(poz * 2, st, mid, nr);
    }

    else
    {
        sum1 += sum[poz * 2];
        return cautArb(poz * 2 + 1, mid + 1, dr, nr);
    }
}

int cautBin(int nr)
{
    if(getSum(1, 1, n, 1, nr) == 0)
        return nr;

    sum1 = 0;

    return cautArb(1, 1, n, nr);
}

void solve()
{
    int i;
    for(i = n; i >= 1; i --)
    {
      //  int locFinal = 1;
        int locFinal = cautBin(v[i]);
        loc[locFinal] = i;

        a = locFinal;
        b = 1;
        baga(1, 1, n);
    }
}

void printFile()
{
    g = fopen("schi.out", "w");

    int i;
    for(i = 1; i <= n; i ++)
        fprintf(g, "%d\n", loc[i]);

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}