Cod sursa(job #1267803)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 20 noiembrie 2014 12:29:10
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <cstdio>
#include <cctype>
#define IN "schi.in"
#define OUT "schi.out"
#define NMAX 30005
#define BUFF 2000
using namespace std;
FILE *in = fopen(IN, "r");
FILE *out = fopen(OUT, "w");
int AIB[NMAX], pozinit[NMAX], fin[NMAX], N;
char buff[BUFF];
int pos = BUFF;
inline char get()
{
    if(pos == BUFF)
        fread(buff, 1, BUFF, in), pos = 0;
    return buff[pos++];
}
inline int readInt()
{
    char c;
    int nr = 0;
    do
    {
        c = get();
    }
    while(!isdigit(c));
    do
    {
        nr = nr * 10 + c - '0';
        c = get();
    }
    while(isdigit(c));
    return nr;
}
inline int lsb(int x)
{
    return (x & (x - 1)) ^ x;
}
void update(int pos, int val)
{
    do
    {
        AIB[pos] += val;
        pos += lsb(pos);
    }
    while(pos <= N);
}
int query(int pos)
{
    int s = 0;
    while(pos)
    {
        s += AIB[pos];
        pos -= lsb(pos);
    }
    return s;
}
void cit()
{
    int i;
    N = readInt();
    for(i = 1; i <= N; ++i)
    {
        pozinit[i] = readInt();
        update(i, 1);
    }
}
void rezolva()
{
    int i, sol, st, dr, mid, p;
    for(i = N; i; --i)
    {
        st = 1;
        dr = N;
        do
        {
            mid = st + ((dr - st) >> 1);
            p = query(mid);
            if(p >= pozinit[i])
            {
                sol = mid;
                dr = mid - 1;
            }
            else
                st = mid + 1;
        }
        while(st <= dr);
        fin[sol] = i;
        update(sol, -1);
    }
}
void afis()
{
    int i;
    for(i = 1; i <= N; ++i)
        fprintf(out, "%d\n", fin[i]);
}
int main()
{
    cit();
    rezolva();
    afis();
    fclose(in);
    fclose(out);
    return 0;
}