Cod sursa(job #3122708)

Utilizator PowerPlantNICOLAS ANDREI MANASIA PowerPlant Data 20 aprilie 2023 10:15:43
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>
#define lsb(x) ((x ^ (x-1)) & x)

using namespace std;
ifstream fin ("order.in");
ofstream fout ("order.out");
int n;
int aib[30030];
bool vis[30030];
void update(int idx,int val)
{
    for(;idx<=n;idx+=lsb(idx))
        aib[idx]+=val;
    return ;
}

int query(int idx)
{
    int sum=0;
    for(;idx>0;idx-=lsb(idx))
        sum+=aib[idx];
    return sum;
}

int look(int k)
{
    int pos=0;
    for(int bit=16;bit>=0;--bit)
    {
        if(pos+(1<<bit)<=n && aib[pos+(1<<bit)]<k){
            pos+=(1<<bit);
            k-=aib[pos];
        }
    }
    return pos+1;

}



int main()
{
    fin>>n;
    for(int i=1;i<=n;++i)
        update(i,1);
    int p=1;
    for(int i=1;i<=n;++i)
    {
        p=(p+i-1)%(n-i+1)+1;
        int x=look(p);
        update(x,-1);
        fout<<x<<" ";
        --p;
    }

    return 0;
}