Cod sursa(job #2844241)

Utilizator CelestinNegraru Celestin Celestin Data 4 februarie 2022 00:08:06
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <fstream>
#define maxi 30005
#define ub(x) ((x^(x-1))&x)
using namespace std;
ifstream f;
ofstream g;
int n,aib[maxi],sol[maxi];
void read()
{
    f.open("order.in",ios::in);
    f>>n;
    f.close();
    return;
}
void update(int x)
{
    for(int i=x;i<=n;i+=ub(i))
        aib[i]--;
    return;
}
int sum(int x)
{
    int suma=0;
    for(int i=x;i>0;i-=ub(i))
        suma+=aib[i];
    return suma;
}
int rez(int x,int mod)
{
    if(!(x%mod))
        return mod;
    return x%mod;
}
int binary(int x)
{
    int st=1,dr=n,pozmin=1000000;
    while(st<=dr)
    {
        int mid=(st+dr)>>1;
        int smid=sum(mid);
        if(smid==x&&mid<pozmin)
            pozmin=mid;
        else if(smid>=x)
            dr=mid-1;
        else st=mid+1;
    }
    return pozmin;
}
void solve()
{
    g.open("order.out",ios::out);
    read();
    for(int i=1;i<=n;i++)
        aib[i]=ub(i);
    int s=2,index=n;
    for(int i=1;i<=n;i++)
    {
        index--;
        int pozitie=binary(s);
        update(pozitie);
        sol[i]=pozitie;
        s+=i;
        if(index)
            s=rez(s,index);
    }
    for(int i=1;i<=n;i++)
        g<<sol[i]<<" ";
    g.close();
    return;
}
int main()
{
    solve();
    return 0;
}