Cod sursa(job #2866392)

Utilizator ANicon111Albu Nicon Georgian ANicon111 Data 9 martie 2022 17:48:13
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 12.91 kb
#include "fstream"
#include "iostream"

namespace containrr{
    using namespace containrr;

    struct Interval{
        unsigned long long start=0, end=0;
        bool onlyStart=false;

        Interval(){}

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

        bool isValid(unsigned long long maxIndex=-1){
            if(start>=maxIndex)
                return false;
            if(end>maxIndex)
                return false;
            if(start>end)
                return false;
            return true;
        }
    };

    template<class T>
    struct Command{
        short id=0;
        Interval interval=Interval(0);
        unsigned long long n=0;
        T *vals=nullptr;

        Command<T>(){

        }

        void del(){
            delete vals;
        }


        template<typename U>
        operator Command<U>(){
            Command<U> newCommand;
            newCommand.id=id;
            newCommand.interval=interval;
            newCommand.n=n;
            newCommand.vals=new U[n];
            for(short i=0;i<n;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.id=1;
        command.vals=new T[1];
        command.vals[0]=val;
        command.n=1;
        command.interval=interval;
        return command;
    }

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

    template <class T=int>
    class PartialSum{
        private:
        unsigned long long *lengths=nullptr, *i=nullptr;
        T *storinator=nullptr;
        Command<T> *commands;
        Interval *intervals;
        short n=0, index=0, intervalToReturn=0;


        void init(){
            i=new unsigned long long[n];
            intervals = new Interval[n];
            commands = new Command<T>[n];
            unsigned long long size=1;
            for(short i=0;i<n;i++)
                size*=lengths[i];
            storinator = new T[size];
        }
        template<typename IntType, typename... Types>
        void init(IntType length, Types... lengths){
            this->lengths[n++]=length;
            init(lengths...);
        }
        void getN(){return;}
        template<typename IntType, typename... Types>
        void getN(IntType length, Types... lengths){
            n++;
            getN(lengths...);
        }


        T getVal(){
            unsigned long long pos=0, factor=1;
            for(short i=0;i<n;i++){
                pos+=this->i[i]*factor;
                factor*=lengths[i];
            }
            if(pos<factor)
                return storinator[pos];
            else
                return 0;
        }
        void setVal(T val){
            unsigned long long pos=0, factor=1;
            for(int i=0;i<n;i++){
                pos+=this->i[i]*factor;
                factor*=lengths[i];
            }
            if(pos<factor)
                storinator[pos]=val;
        }
        void addVal(T val){
            unsigned long long pos=0, factor=1;
            for(int i=0;i<n;i++){
                pos+=this->i[i]*factor;
                factor*=lengths[i];
            }
            if(pos<factor)
                storinator[pos]+=val;
        }
        bool stateIsValid(){
            if(index!=n)
                return false;
            for(short i=0;i<n;i++){
                if(!intervals[i].isValid(lengths[i]))
                    return false;
                if(commands[i].id){
                    if(commands[i].id!=1&&commands[i].id!=2)
                        return false;
                    if(!commands[i].interval.isValid(lengths[i]))
                        return false;
                }
            }
            return true;
        }
        void reset(){
            index=0;
            intervalToReturn=0;
            for(int i=0;i<n;i++){
                this->i[i]=0;
                intervals[i]=Interval(0);
                commands[i].id=0;
                if(commands[i].vals)
                    delete commands[i].vals;
                commands[i].vals=nullptr;
            }
        }

        unsigned long long getBiggestPow(unsigned long long val){
            unsigned long long pow=1;
            while((pow<<1)<=val)
                pow<<=1;
            return pow;
        }

        void add(T x, short dim){
            unsigned long long pow=1, oldI=i[dim];
            while(i[dim]<lengths[dim]){
                if((i[dim]+1)%pow){
                    if(dim>0){
                        add(x, dim-1);
                    }else{
                        addVal(x);
                    }
                    i[dim]+=pow>>1;
                }
                pow=pow<<1;
            }
            i[dim]=oldI;
        }

        void addInterval(T x, short dim, bool equals=false){
            unsigned long long start=intervals[dim].start, end=intervals[dim].end;
            for(unsigned long long j=start;j<end;j++){
                Interval temp=intervals[dim];
                i[dim]=j;
                intervals[dim]=Interval(j, j+1);
                if(dim==0){
                    T val=x;
                    if(equals)
                        val-=getInterval();
                    add(val,n-1);
                }else
                    addInterval(x,dim-1,equals);
                intervals[dim]=temp;
            }
        }

        T get(short dim){
            unsigned long long end=intervals[dim].end, oldI=i[dim];
            T sum=0;
            i[dim]=-1;
            for(unsigned long long pow=getBiggestPow(lengths[dim]);pow>0;pow=pow>>1){
                if(i[dim]+pow<end){
                    i[dim]+=pow;
                    dim==0 ? sum+=getVal() : sum+=get(dim-1);
                }

            }
            i[dim]=oldI;
            return sum;
        }

        T getInterval(short i=0){
            T val=0;
            val+=get(n-1);
            for(;i<n;i++){
                unsigned long long temp=intervals[i].end;
                intervals[i].end=intervals[i].start;
                val-=getInterval(i+1);
                intervals[i].end=temp;
            }
            return val;
        }

        void getLowerBound(T val, short dim){
            bool optimized=true;
            if(commands[dim].interval.start>0)
                optimized=false;
            for(short i=0;i<n;i++)
                if(intervals[i].end>1){
                        optimized=false;
                        break;
                }
            if(optimized){
                intervals[dim].start=commands[dim].interval.start;
                i[dim]=-1;
                T sum=0;
                for(unsigned long long pow=getBiggestPow(commands[dim].interval.end);pow>0&&i[dim]+pow>=commands[dim].interval.start;pow=pow>>1){
                    i[dim]+=pow;
                    sum+=getVal();
                    if(i[dim]>=commands[dim].interval.end-1||sum>=val){
                        sum-=getVal();
                        i[dim]-=pow;
                    }
                }
                intervals[dim].end=i[dim]+1;
            }else{
                intervals[dim].start=commands[dim].interval.start;
                intervals[dim].end=0;
                for(unsigned long long pow=getBiggestPow(intervals[dim].end);pow>0&&intervals[dim].end+pow>commands[dim].interval.start;pow=pow>>1){
                    intervals[dim].end+=pow;
                    if(intervals[dim].end>=commands[dim].interval.end||getInterval()>=val)
                        intervals[dim].end-=pow;
                }
            }
            if(intervals[dim].end==0)
                intervals[dim].end=intervals[dim].start;
            intervals[dim].end++;
        }

        void getUpperBound(T val, short dim){
            bool optimized=true;
            if(commands[dim].interval.start>0)
                optimized=false;
            for(short i=0;i<n;i++)
                if(intervals[i].end>1){
                        optimized=false;
                        break;
                }
            if(optimized){
                intervals[dim].start=commands[dim].interval.start;
                i[dim]=-1;
                T sum=0;
                for(unsigned long long pow=getBiggestPow(commands[dim].interval.end);pow>0&&i[dim]+pow>=commands[dim].interval.start;pow=pow>>1){
                    i[dim]+=pow;
                    sum+=getVal();
                    if(i[dim]>=commands[dim].interval.end-1||sum>val){
                        sum-=getVal();
                        i[dim]-=pow;
                    }
                }
                intervals[dim].end=i[dim]+1;
            }else{
                intervals[dim].start=commands[dim].interval.start;
                intervals[dim].end=0;
                for(unsigned long long pow=getBiggestPow(lengths[dim]);pow>0&&intervals[dim].end+pow>commands[dim].interval.start;pow=pow>>1){
                    intervals[dim].end+=pow;
                    if(intervals[dim].end>=commands[dim].interval.end||getInterval()>val)
                        intervals[dim].end-=pow;
                }
            }
            if(intervals[dim].end==0)
                intervals[dim].end=intervals[dim].start;
            intervals[dim].end++;
        }

        void evalCommands(){
            for(short i=0;i<n;i++)
                if(commands[i].id)
                    switch (commands[i].id)
                    {
                    case 1:
                        intervalToReturn=i;
                        if(commands[i].interval.onlyStart)
                            commands[i].interval.end=lengths[i];
                        getLowerBound(commands[i].vals[0], i);
                        break;
                    case 2:
                        intervalToReturn=i;
                        if(commands[i].interval.onlyStart)
                            commands[i].interval.end=lengths[i];
                        getUpperBound(commands[i].vals[0], i);
                        break;
                    default:
                        break;
                    }
        }

        public:
        template<typename... Types>
        PartialSum(Types... lengths){
            getN(lengths...);
            this->lengths=new unsigned long long[n];
            n=0;
            init(lengths...);
        }

        T debugval(T newval=0){
            if(stateIsValid()){
                if(newval){
                    setVal(newval);
                    return 0;
                }
                return getVal();
            }
            return 0;
        }

        operator T(){
            T val=0;
            evalCommands();
            if(stateIsValid())
                val=getInterval();
            reset();
            return val;
        }

        operator Interval(){
            evalCommands();
            Interval interval=intervals[intervalToReturn];
            reset();
            return interval;
        }

        PartialSum &operator[](long long pos) {
            intervals[index++]=Interval(pos,pos+1);
            return *this;
        }

        PartialSum &operator[](Interval pos) {
            intervals[index]=Interval(pos.start,pos.onlyStart?lengths[index]:pos.end);
            index++;
            return *this;
        }

        PartialSum &operator[](Command<T> command) {
            intervals[index]=Interval(0,1);
            commands[index++]=command;
            return *this;
        }

        void operator+=(T x){
            evalCommands();
            if(stateIsValid())
                addInterval(x,n-1);
            reset();
        }

        void operator-=(T x){
            evalCommands();
            if(stateIsValid())
                addInterval(-x,n-1);
            reset();
        }

        void operator=(T x){
            evalCommands();
            if(stateIsValid()){
                addInterval(x,n-1,true);
            reset();
            }
        }

        T *memDump(){
            return storinator;
        }

        void del(){
            delete[] storinator;
            delete[] intervals;
            delete[] commands;
            delete[] lengths;
            delete[] i;
        }
    };
}

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