Cod sursa(job #947009)

Utilizator costyv87Vlad Costin costyv87 Data 6 mai 2013 15:33:17
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
//HighFlow
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <fstream>
#include <string.h>
#include <math.h>
#include <algorithm>
#define fcat(c) while (c!='\n') fscanf(f,"%c",&c)
#define cat(c) while (c!='\n') scanf("%c",&c)
#define For(i,st,dr,k) for (int i=(st);i<=(dr);i+=(k))
#define ll (long long)
#define kfl(i,j) (a[(i)][(j)].c-a[(i)][(j)].f)
using namespace std;
FILE *f,*g;
int r,n,i,j;
int t[30100],sol[30100],v[30100];


void update(int p,int x)
{
    int i;

    for (i=p;i<=n;i+=i&(-i))
        t[i]+=x;
}

int query(int poz)
{
    int s=0,i;
    for (i=poz;i>0;i-=i&(-i))
        s=s+t[i];
    return s;
}

int caut(int st,int dr,int x)
{
   int m,j;

   if (st<=dr)
   {
       m=(st+dr)/2;
       j=query(m);
       if (j==x)
        return min(m,caut(st,m-1,x));
       if (j<x)
        return (caut(m+1,dr,x));
       else
        return (caut(st,m-1,x));
   }
   else
    return 100000;
}


int main()
{
    f=fopen("schi.in","r");
    g=fopen("schi.out","w");

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

    for (r=1;r*2<=n; r*=2);

    for (i=1;i<=n;i++) update(i,1);

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

    for (i=n;i>=1;i--)
    {
        j=caut(1,n,v[i]);
        update(j,-1);
        sol[j]=i;
    }

    for (i=1;i<=n;i++) fprintf(g,"%d\n",sol[i]);

	return 0;
}