Cod sursa(job #2954371)

Utilizator vlad79xVlad79X vlad79x Data 14 decembrie 2022 08:20:52
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;
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 search(int x) {
                int s=0,ans=0;
                for(int i=15; i>=0; i--) {
                        if(ans+(1<<i)<=n&&s+aib[ans+(1<<i)]<=x) {
                                s+=aib[ans+(1<<i)];
                                ans+=(1<<i);
                        }
                        //cout<<ans<<" "<<s<<" ";
                }
                //cout<<'\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;
        }
        return 0;
}