Cod sursa(job #2034406)

Utilizator Coroian_DavidCoroian David Coroian_David Data 7 octombrie 2017 19:26:58
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 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 aib[MAX_N + 1];

int loc[MAX_N + 1];

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

    n = getNr();

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

    fclose(f);
}

int suma(int a)
{
    int rez = 0;

    while(a > 0)
    {
        rez += aib[a];

        a = a & (a - 1);
    }

    return rez;
}

void baga(int a, int nr)
{
    while(a <= n)
    {
        aib[a] += nr;

        a += a & (-a);
    }
}

int cautBin(int nr)
{
    if(suma(nr) == nr)
        return nr;

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

    while(pas != 0 && nr > 0)
    {
        if(i + pas <= n && aib[i + pas] < nr)
        {
            nr -= aib[i + pas];

            i += pas;
        }

        pas >>= 1;
    }

    return i + 1;
}

void solve()
{
    int i;
    for(i = 1; i <= n; i ++)
        baga(i, 1);

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

        //printf("AVME %d\n", locFinal);

        baga(locFinal, -1);
    }
}

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