Cod sursa(job #551355)

Utilizator acelasi7Tudor Maxim acelasi7 Data 10 martie 2011 17:40:16
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<stdio.h>
using namespace std;
#define zzz(x) ((x^(x-1))&x)
#define nrn 30005
FILE *in=fopen("schi.in","r"),*out=fopen("schi.out","w");
int AIB[nrn],ord[nrn],n;
int MS[nrn];//mystack
void update(int i,int val)
{
    for(i=i;i<=n;i+=zzz(i))
        AIB[i]+=val;
}
int suma(int i)
{
    int sum=0;
    for(i=i;i>0;i-=zzz(i))
        sum+=AIB[i];
    return sum;
}
void search(int val,int i)
{
    int mid,left,right;
    left=1;right=n;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(val==suma(mid) && !ord[mid])
        {
            update(mid,-1);
            ord[mid]=i;
            return ;
        }
        if(val<=suma(mid))
            right=mid-1;
        else left=mid+1;
    }
}
int main()
{
    int i;
    fscanf(in,"%d",&n);
    for(i=1;i<=n;++i)
        update(i,1);
    for(i=1;i<=n;++i)
        fscanf(in,"%d",&MS[i]);
    for(i=n;i>0;--i)
        search(MS[i],i);
    for(i=1;i<=n;++i)
        fprintf(out,"%d\n",ord[i]);
    return 0;
}