Cod sursa(job #2862993)

Utilizator ANicon111Albu Nicon Georgian ANicon111 Data 6 martie 2022 10:49:12
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.41 kb
#include "fstream"
#include "iostream"

namespace containrr{
using namespace containrr;

struct Command{
    short command=-1;
    long long val=0;
    Command(short commandID, long long value=0){
        command=commandID;
        val=value;
    }
};

Command lowerBound(long long val){
    return Command(1,val);
}

Command upperBound(long long val){
    return Command(2,val);
}

template <class T=int>
class BinaryPartialSum{
    private:
    long long *dims=nullptr, *powsOf2=nullptr, *modif=nullptr, *currentPos=nullptr, commandValue=0;
    T *tree=nullptr;
    short dimNR=0,currentPosIndex=0, commandDim=-1, command=-1;

    bool checkCurrentPosValidity(){
        if(currentPosIndex!=dimNR)
            return 0;
        for(short i=0;i<dimNR;i++)
            if(currentPos[i]>=dims[i])
                return 0;
        return 1;
    }

    long long basePos(short dim){
        long long sum=0;
        for(short i=dimNR-1;i>dim;i--)
            sum+=modif[i]*currentPos[i];
        return sum;
    }

    void add(T x, short dim=-1){
        if(dim==-1)
            dim=dimNR-1;
        long long i=currentPos[dim], bkp=currentPos[dim], pow=1, base=basePos(dim);
        while(i<dims[dim]){
            if((i+1)%pow){
                currentPos[dim]=i;
                if(dim>0){
                    add(x, dim-1);
                }else
                    tree[base+i]+=x;
                i+=pow>>1;
            }
            pow=pow<<1;
        }
        currentPos[dim]=bkp;
    }

    long long get(short dim){
        long long pos=currentPos[dim]+1, base=basePos(dim), sum=0;
        currentPos[dim]=-1;
        for(long long pow=1ll<<powsOf2[dim];pow>0;pow=pow>>1){
            if(currentPos[dim]+pow<pos){
                currentPos[dim]+=pow;
                dim==0 ? sum+=tree[base+currentPos[dim]] : sum+=get(dim-1);
            }
            
        }
        currentPos[dim]=pos-1;
        return sum;
    }

    void init(){
        powsOf2=new long long[dimNR];
        modif=new long long[dimNR];
        currentPos=new long long[dimNR];
        long long factor=1;
        for(int i=0;i<dimNR;i++){
            modif[i]=factor;
            factor*=dims[i];
            while((1ll<<powsOf2[i])<=dims[i])
                powsOf2[i]++;
            powsOf2[i]--;
        }
        tree = new T[factor];
    }

    void getDimensions(){
        init();
    }

    template<typename IntType, typename... Types>
    void getDimensions(IntType length, Types... lengths){
        dims[dimNR++]=length;
        getDimensions(lengths...);
    }

    void getDimNR(){return;}

    template<typename IntType, typename... Types>
    void getDimNR(IntType length, Types... lengths){
        dimNR++;
        getDimNR(lengths...);
    }

    long long getLowerBound(T val){
        int i=-1;
        long long sum=0;
        for(long long pow=1ll<<powsOf2[commandDim];pow>0;pow=pow>>1){
            if(i+pow<dims[commandDim]&&sum+tree[i+pow]<val){
                i+=pow;
                sum+=tree[i];
            }
        }
        return i+1;
    }

    long long getUpperBound(T val){
        currentPos[commandDim]=-1;
        for(long long pow=1ll<<powsOf2[commandDim];pow>0;pow=pow>>1){
            currentPos[commandDim]+=pow;
            if(currentPos[commandDim]>=dims[commandDim]||get(dimNR-1)>=val+1)
                currentPos[commandDim]-=pow;
        }
        return currentPos[commandDim]+1;
    }

    public:
    template<typename... Types>
    BinaryPartialSum(Types... lengths){
        getDimNR(lengths...);
        dims=new long long[dimNR];
        dimNR=0;
        getDimensions(lengths...);
    }

    T debugval(T newval=0){
        if(newval){
            tree[basePos(0)+currentPos[0]]=newval;
            return 0;
        }
        if(checkCurrentPosValidity()){
            return tree[basePos(0)+currentPos[0]];
        }
        return 0;
    }

    operator long long(){
        long long val=0;
        if(checkCurrentPosValidity())
            switch (command)
            {
            case 1:
                val=getLowerBound(commandValue);
                break;
            case 2:
                val=getUpperBound(commandValue);
                break;
            default:
                val=get(dimNR-1);
                break;
            }
        currentPosIndex=0;
        command=-1;
        commandDim=-1;
        commandValue=0;
        return val;
    }

    BinaryPartialSum &operator[](long long pos) {
        currentPos[currentPosIndex++]=pos;
        return *this;
    }

    BinaryPartialSum &operator[](Command command) {
        this->command=command.command;
        this->commandValue=command.val;
        commandDim=currentPosIndex;
        currentPos[currentPosIndex++]=0;
        return *this;
    }

    void operator+=(T x){
        if(checkCurrentPosValidity())
            add(x);
        currentPosIndex=0;
    }

    void operator-=(T x){
        if(checkCurrentPosValidity())
            add(-x);
        currentPosIndex=0;
    }
};

}

long long pos[30000],sol[30000];
 
int main(){
    using namespace std;
    using namespace containrr;
    ifstream in("schi.in");
    ofstream out("schi.out");
    int n;
    in>>n;
    BinaryPartialSum<long long> v(n);
    for(int i=0;i<n;i++){
        in>>pos[i];
        v[i]+=1;
    }
    for(int i=n-1;i>=0;i--){
        int currpos=v[lowerBound(pos[i])];
        cout<<currpos<<" ";
        sol[currpos]=i+1;
        v[currpos]-=1;
    }
    for(int i=0;i<n;i++)
        out<<sol[i]<<"\n";
    out<<flush;
}