Cod sursa(job #2680457)

Utilizator eugen5092eugen barbulescu eugen5092 Data 3 decembrie 2020 16:29:43
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <bits/stdc++.h>
using namespace std;

ifstream ci("order.in");
ofstream cou("order.out");

int n,N;
int aint[30005];


void cit(){
    int i;
    ci>>n;
    N=1;
    while(N<n){
        N*=2;
    }
    for(i=N;i<N+n;i++){
        aint[i]=1;
    }
    for(i=N-1;i;i--){
        aint[i]=aint[2*i]+aint[2*i+1];
    }
}



void Update(int p, int x)
{
    int t, mx;
    p = p + N - 1;
    aint[p] = x;
    while(p > 0)
    {
        t = p / 2;
        mx = aint[2 * t]+aint[2 * t + 1];
        aint[t] = mx;
        p = t;
    }

}

int Query(int nod, int x, int y, int st, int dr)
{
    int m;
    if(st == x && dr == y) return aint[nod];
    else
    {
        m = (st + dr) / 2;
        if(y <= m) return Query(nod * 2, x, y, st, m);
        else if(m + 1 <= x) return Query(nod * 2 + 1, x, y, m + 1, dr);
        else return Query(nod * 2, x, m, st, m)+Query(nod * 2 + 1, m + 1, y, m + 1, dr);
    }
}

int cauta(int a,int x){
    int aux,st=a,dr=n,mij,sol=n,t;

    t=(a>=2?Query(1,1,a-1,1,N):0);
    while(st<=dr){

        mij=(st+dr)/2;

        aux=Query(1,1,mij,1,N)-t ;
        //cout<<a<<" "<<x<<" "<<st<<" "<<dr<<" "<<aux<<"\n";
        if(aux>=x){
            dr=mij-1;
            sol=mij;
            //cout<<"la dr \n";
        }else{
            st=mij+1;
            //cout<<"la st \n";
        }
        //cout<<st<<" "<<dr<<"\n";
    }
    return sol;
}

void rez(){

    int k=1,p=n,rest,x=1;
    ///p=cat oameni am in tot
    ///k=cati pasi fac
    ///h=cat mai am pana la cap
    for(int i=1;i<=n;i++){

        int h=Query(1,x+1,n,1,N);
        //cout<<i<<" "<<h<<" "<<k<<" **** \n";
        if(k<h){
            x=cauta(x+1,k);
            Update(x,0);
        }else{
        int k1=k;
        k1-=h;
        if(k1%p==0){
            rest=p;
        }else{
            rest=k1%p;
        }
            x=cauta(1,rest);
            Update(x,0);
        }
        cou<<x<<" ";
        p--;
        k++;
    }
}

int main()
{
    cit();
    rez();
    return 0;
}