Cod sursa(job #2960347)

Utilizator vlad79xVlad79X vlad79x Data 4 ianuarie 2023 02:53:53
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax=1e5;
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 search(int x) {
                int s=0,ans=0;
                for(int i=24; i>=0; i--) {
                        if((ans+(1<<i)<=n && s+aib[ans+(1<<i)]<x)) {
                                s+=aib[ans+(1<<i)];
                                ans+=(1<<i);
                        }
                }
                ans++;
                if(ans>n)
                        return -1;
                if(queryPref(n)==x)
                        return n;
                return ans;
        }
};
int main() {
        ifstream cin("order.in");
        ofstream cout("order.out");
        AIB aib;
        int n,poz=2,pozs,rem;
        cin>>n;
        rem=n;
        aib.n=n;
        for(int i=1; i<=n; i++)
                aib.update(i,1);
        for(int i=1; i<=n; i++) {
                pozs=aib.search(poz);
                cout<<pozs<<" ";
                aib.update(pozs,-1);
                poz+=i;
                rem--;
                if(rem>0)
                        poz%=rem;
                //      cout<<poz<<"\n";
        }
        return 0;
}