Cod sursa(job #2667303)

Utilizator MohneaGosuMihnea Gusu MohneaGosu Data 3 noiembrie 2020 12:10:45
Problema Schi Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>

using namespace std;
ifstream Gigi ("schi.in");
ofstream Marcel ("schi.out");
int a[65537];
int v[30000];
int f[30000];
int n,n1;
int binary(int x)
{
    x--;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x++;
    return x;
}
void build ()
{
    int i;
    for (i=n1;i<n+n1;i++){
        a[i]=1;
    }
    for (i=n1-1;i>=1;i--){
        a[i]=a[2*i]+a[2*i+1];
    }
}
void update()
{
    int i;
    for (i=n1-1;i>=1;i--){
        a[i]=a[2*i]+a[2*i+1];
    }
}
void cauta (int x,int poz)
{
    int i=1;
    while (i<n+n1){
        if(a[i]==x && i>=n1){
            a[i]=0;
            f[i-n1]=poz+1;
            update();
            return;
        }
        if (a[2*i]<x){
            x-=a[2*i];
            i*=2;
            i+=1;
        }
        else{
            i*=2;
        }
    }
}
int main()
{
    Gigi>>n;
    n1=binary(n);
    int i;
    for (i=0;i<n;i++){
        Gigi>>v[i];
    }
    build();
    f[v[n-1]-1]=n;
    a[n1+v[n-1]-1]=0;
    update();
    for (i=n-2;i>=0;i--){
        cauta(v[i],i);
    }
    for (i=0;i<n;i++){
        Marcel<<f[i]<<"\n";
    }
    return 0;
}