Cod sursa(job #2864352)

Utilizator ANicon111Albu Nicon Georgian ANicon111 Data 7 martie 2022 20:00:36
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 10.92 kb
#include "fstream"
#include "iostream"

namespace containrr{
using namespace containrr;

struct Interval{
    unsigned long long start=0, end=0;
    bool onlyStart=false;
    Interval(unsigned long long start){
        this->start=start;
        onlyStart=true;
    }
    Interval(unsigned long long start, unsigned long long end){
        this->start=start;
        this->end=end;
    }
};

template<class T>
struct Command{
    short command=0;
    Interval commandInterval=Interval(0);
    unsigned long long valNR=0;
    T *vals=nullptr;
    void del(){
        delete vals;
    }
    template<typename U>
    operator Command<U>(){
        Command<U> newCommand;
        newCommand.command=command;
        newCommand.commandInterval=commandInterval;
        newCommand.valNR=valNR;
        newCommand.vals=new U[valNR];
        for(short i=0;i<valNR;i++)
            newCommand.vals[i]=vals[i];
        delete vals;
        return newCommand;
    }
};

template <typename T>
Command<T> lowerBound(T val, Interval interval=Interval(0)){
    Command<T> command;
    command.command=1;
    command.vals=new T[1];
    command.vals[0]=val;
    command.valNR=1;
    command.commandInterval=interval;
    return command;
}

template <typename T>
Command<T> upperBound(T val, Interval interval=Interval(0)){
    Command<T> command;
    command.command=2;
    command.vals=new T[1];
    command.vals[0]=val;
    command.valNR=1;
    command.commandInterval=interval;
    return command;
}

template <class T=int>
class BinaryPartialSum{
    private:
    unsigned long long *dims=nullptr, *powsOf2=nullptr, *modif=nullptr, *currentPos=nullptr, *currentStartPos=nullptr;
    T *tree=nullptr;
    short dimNR=0, currentPosIndex=0, commandDim=0;
    Command<T> currentCommand;

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

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

    unsigned long long basePos(short dim){
        unsigned 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;
        unsigned 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;
    }

    T get(short dim){
        unsigned long long pos=currentPos[dim]+1, base=basePos(dim);
        T sum=0;
        currentPos[dim]=-1;
        for(unsigned long long pow=1ull<<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;
    }

    T getInterval(short dim, short i=0){
        T val=0;
            val+=get(dimNR-1);
        for(;i<dimNR;i++){
            unsigned long long temp=currentPos[i];
            currentPos[i]=currentStartPos[i]-1;
            val-=getInterval(dimNR, i+1);
            currentPos[i]=temp;
        }
        return val;
    }

    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...);
    }

    Interval getLowerBound(T val){
        bool isOnFirstDim=true;
        for(short i=0;i<dimNR;i++){
            if(currentPos[i]>0||currentStartPos[i]>0)
                isOnFirstDim=false;
        }
        if(isOnFirstDim){
            unsigned long long i=-1;
            T sum=0;
            for(long long pow=1ull<<powsOf2[commandDim];pow>0&&i+pow>=currentCommand.commandInterval.start;pow=pow>>1){
                if(i+pow<dims[commandDim]&&i+pow<currentCommand.commandInterval.end&&sum+tree[(i+pow)*modif[commandDim]]<val){
                    i+=pow;
                    sum+=tree[i*modif[commandDim]];
                }
            }
            return Interval(currentStartPos[commandDim], i+1);
        }else{
            currentPos[commandDim]=-1;
            for(unsigned long long pow=1ull<<powsOf2[commandDim];pow>0&&currentPos[commandDim]+pow>=currentCommand.commandInterval.start;pow=pow>>1){
                currentPos[commandDim]+=pow;
                if(currentPos[commandDim]>=dims[commandDim]||currentPos[commandDim]>=currentCommand.commandInterval.end||getInterval(dimNR-1)>=val)
                    currentPos[commandDim]-=pow;
            }
            return Interval(currentStartPos[commandDim], currentPos[commandDim]+1);
        }
    }

    Interval getUpperBound(T val){
        bool isOnFirstDim=true;
        for(short i=0;i<dimNR;i++){
            if(currentPos[i]>0||currentStartPos[i]>0)
                isOnFirstDim=false;
        }
        if(isOnFirstDim){
            unsigned long long i=-1;
            T sum=0;
            for(unsigned long long pow=1ull<<powsOf2[commandDim];pow>0&&i+pow>=currentCommand.commandInterval.start;pow=pow>>1){
                if(i+pow<dims[commandDim]&&i+pow<currentCommand.commandInterval.end&&sum+tree[(i+pow)*modif[commandDim]]<=val){
                    i+=pow;
                    sum+=tree[i*modif[commandDim]];
                }
            }
            return Interval(currentStartPos[commandDim], i+1);
        }else{
            currentPos[commandDim]=-1;
            for(unsigned long long pow=1ull<<powsOf2[commandDim];pow>0&&currentPos[commandDim]+pow>=currentCommand.commandInterval.start;pow=pow>>1){
                currentPos[commandDim]+=pow;
                if(currentPos[commandDim]>=dims[commandDim]||currentPos[commandDim]>=currentCommand.commandInterval.end||getInterval(dimNR-1)>val)
                    currentPos[commandDim]-=pow;
            }
            return Interval(currentStartPos[commandDim], currentPos[commandDim]+1);
        }
    }

    public:
    template<typename... Types>
    BinaryPartialSum(Types... lengths){
        getDimNR(lengths...);
        dims=new unsigned 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 T(){
        T val=0;
        if(checkCurrentPosValidity())
            switch (currentCommand.command)
            {
            default:
                val=getInterval(dimNR-1);
                break;
            }
        for(short i=0;i<dimNR;i++)
            currentStartPos[i]=0;
        currentPosIndex=0;
        currentCommand.command=-1;
        commandDim=-1;
        if(currentCommand.vals)
            delete currentCommand.vals;
        currentCommand.vals=nullptr;
        return val;
    }

    operator Interval(){
        Interval val(0);
        if(checkCurrentPosValidity())
            switch (currentCommand.command)
            {
            case 1:
                if(currentCommand.commandInterval.onlyStart)
                    currentCommand.commandInterval.end=dims[commandDim]-1;
                currentPos[commandDim]=0;
                val=getLowerBound(currentCommand.vals[0]);
                break;
            case 2:
                if(currentCommand.commandInterval.onlyStart)
                    currentCommand.commandInterval.end=dims[commandDim]-1;
                currentPos[commandDim]=0;
                val=getUpperBound(currentCommand.vals[0]);
                break;
            default:
                break;
            }
        for(short i=0;i<dimNR;i++)
            currentStartPos[i]=0;
        currentPosIndex=0;
        currentCommand.command=-1;
        currentCommand.commandInterval=Interval(-1,-1);
        commandDim=-1;
        if(currentCommand.vals)
            delete currentCommand.vals;
        currentCommand.vals=nullptr;
        return val;
    }

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

    BinaryPartialSum &operator[](Interval pos) {
        currentPos[currentPosIndex]=pos.onlyStart?dims[currentPosIndex]-1:pos.end;
        currentStartPos[currentPosIndex++]=pos.start;
        return *this;
    }

    BinaryPartialSum &operator[](Command<T> command) {
        this->currentCommand=command;
        commandDim=currentPosIndex;
        currentStartPos[currentPosIndex]=currentCommand.commandInterval.start;
        if(currentCommand.commandInterval.onlyStart)
            currentCommand.commandInterval.end=dims[currentPosIndex]-1;
        currentPos[currentPosIndex++]=currentCommand.commandInterval.end;
        return *this;
    }

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

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

    void operator=(T x){
        if(checkCurrentPosValidity()){
            for(short i=0;i<dimNR;i++)
                currentStartPos[i]=currentPos[i];
            x-=getInterval(dimNR-1);
            add(x);
        }
        currentPosIndex=0;
    }

    T *memDump(){
        return tree;
    }

    void del(){
        delete dims;
        delete powsOf2;
        delete modif;
        delete currentPos;
        delete currentStartPos;
        delete tree;
    }
};

}

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--){
        Interval currpos=v[lowerBound(pos[i])];
        cout<<currpos.end<<" ";
        sol[currpos.end]=i+1;
        v[currpos.end]-=1;
    }
    for(int i=0;i<n;i++)
        out<<sol[i]<<"\n";
    out<<flush;
}