Cod sursa(job #2667293)

Utilizator MohneaGosuMihnea Gusu MohneaGosu Data 3 noiembrie 2020 12:01:23
Problema Schi Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 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)
{
    int x1=x;
    while (x1>1){
        if (x1%2==0) x1/=2;
        else break;
    }
    if (x1!=1){
        int power = 1;
        while(power < x) power*=2;
        return power;
    }
    else 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;
}