Cod sursa(job #2970130)

Utilizator vlad79xVlad79X vlad79x Data 24 ianuarie 2023 12:32:07
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>

using namespace std;
ifstream gaina("order.in");
ofstream vultur("order.out");

const int nmax=100000;
int lsb(int x) {return x&(-x);}

struct AIB {
        int aib[nmax+1],n;
        void update(int poz,int val) {
                for(; poz<=n; poz+=lsb(poz))
                        aib[poz]+=val;
        }
        int queryPref(int poz) {
                int s=0;
                for(; poz>0; poz-=lsb(poz))
                        s+=aib[poz];
                return s;
        }
        int query(int st,int dr) {
                return queryPref(dr)-queryPref(st-1);
        }
        int searchX(int x) {
                if(x==0)
                        x=1;
                int s=0,ans=0;
                for(int i=20; i>=0; i--) {
                        if(ans+(1<<i)<=n && s+aib[ans+(1<<i)]<x) {
                                s+=aib[ans+(1<<i)];
                                ans+=(1<<i);
                        }
                }
                if(ans==n)
                        ans--;
                return ans+1;
        }
};

int main() {
        AIB aib;
        int n,rem,poz,who=-1;
        gaina>>n;
        aib.n=n;
        for(int i=1; i<=n; i++)
                aib.update(i,1);
        rem=n;
        poz=1;
        for(int pas=1; pas<=n; pas++) {
                poz=aib.queryPref(poz)+pas;
                if(poz>rem&&rem>0)
                        poz%=rem;
                rem--;
                who=aib.searchX(poz);
                aib.update(who,-1);
                vultur<<who<<" ";
        }
        vultur<<'\n';
        return 0;
}