Cod sursa(job #2034239)

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

#define MAX_N 30000

using namespace std;

FILE *f, *g;

int n;

int v[MAX_N + 1];
int aib[MAX_N + 1];

int loc[MAX_N + 1];

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

    fscanf(f, "%d", &n);

    int i;
    for(i = 1; i <= n; i ++)
    {
        fscanf(f, "%d", &v[i]);
    }

    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)
        {
          //  printf("REVINE %d   ", nr + i + pas);
         //   printf("AVEM SUMA %d %d\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 --)
    {
  /*      if(loc[1] == 0 && v[i] == 1)
        {
            loc[1] = i;

            baga(1);
        }
*/
        //else
      //  {
         //   printf("INTRA %d %d\n", i, suma(4));

            int locFinal = cautBin(v[i]);
            loc[locFinal] = i;

           // printf("BAGAM %d\n", locFinal);
            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;
}