Cod sursa(job #2034245)

Utilizator Coroian_DavidCoroian David Coroian_David Data 7 octombrie 2017 17:19:24
Problema Schi Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <bits/stdc++.h>

#define MAX_N 30000

using namespace std;

FILE *f, *g;

int crChar = 262144;

const int buffSize = 262144;

char buff[262150];

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)
{
    while(a <= n)
    {
        aib[a] ++;

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

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

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

    while(pas != 0)
    {
        if(nr + i + pas <= n && suma(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 = cautBin(v[i]);
        loc[locFinal] = i;

        baga(locFinal);
    }
}

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