Cod sursa(job #2034270)

Utilizator Coroian_DavidCoroian David Coroian_David Data 7 octombrie 2017 17:43:16
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.78 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 cautBin(int nr)
{
    if(getSum(1, 1, n, 1, nr) == 0)
        return nr;

    int i = 0;
    int pas = (1 << 14);

    while(pas != 0)
    {
        if(nr + i + pas <= n && getSum(1, 1, n, 1, nr + i + pas) > i + pas)
            i += pas;

        pas >>= 1;
    }

    return nr + i + 1;
}

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;
}