Cod sursa(job #1554351)

Utilizator daneel95Holteiu Daniel-Ninel daneel95 Data 21 decembrie 2015 12:08:10
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <fstream>
#define tata(x) (x)/2
#define fst(x) (x)<<1
#define fdr(x) ((x)<<1)+1

using namespace std;

ifstream in("schi.in");
ofstream out("schi.out");

int n;
int partial[30005];
int final[30005];
int arbint[4*30005];

void create_atbint(int poz,int st,int dr)
{
    if(st==dr){
        arbint[poz]=1;
        return;
    }
    int mij=(st+dr)/2;
    create_atbint(fst(poz),st,mij);
    create_atbint(fdr(poz),mij+1,dr);
    arbint[poz]=dr-st+1;
}

void update(int poz,int st,int dr,int vpoz,int val)
{
    if(st==dr){
        arbint[poz]=0;
        final[st]=val;
        return;
    }
    int mij = (st+dr)/2;
    if(vpoz <= arbint[fst(poz)]) update(fst(poz),st,mij,vpoz,val);
        else update(fdr(poz),mij+1,dr,vpoz-arbint[fst(poz)],val);
    arbint[poz]--;
}

int main()
{
    int i,j,nr=0,x;
    in>>n;
    for(i=1;i<=n;i++) in>>partial[i];
    create_atbint(1,1,n);
    for(i=n;i>=1;i--) update(1,1,n,partial[i],i);
    for(i=1;i<=n;i++) out<<final[i]<<"\n";
    in.close();
    out.close();
    return 0;
}



//80 pct
/*#include <fstream>

using namespace std;

ifstream in("schi.in");
ofstream out("schi.out");

int n;
int partial[30005];
int final[30005];

int cautare(int x)
{
    if(final[x]!=0) return x;
    return 0;
}
int main()
{
    int i,j,nr=0,x;
    in>>n;
    for(i=1;i<=n;i++) in>>partial[i];

    for(i=1;i<=n;i++)
    {
        x=cautare(partial[i]);
        if(x)
        {
            for(j=nr;j>=x;j--)
                final[j+1]=final[j];
        }
        final[partial[i]]=i;
        nr++;
    }
    for(i=1;i<=n;i++) out<<final[i]<<"\n";
    in.close();
    out.close();
    return 0;
}*/