Cod sursa(job #2490044)

Utilizator stefan1anubystefan popa stefan1anuby Data 9 noiembrie 2019 17:17:39
Problema Order Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <algorithm>
#include <string>
using namespace std;
ifstream cin("order.in");
ofstream cout("order.out");
#define zeros(x) (x^(x-1))&x
int aib[30005],n;
inline void Add(int x, int q)
{
    int i;
    for(i=x; i<=n; i+=zeros(i))
        aib[i]+=q;
}
inline int Sum(int x)
{
    int i,sum=0;
    for(i=x; i>0; i-=zeros(i))
        sum+=aib[i];
    return sum;
}
inline int Caut_Bin(int x)
{
    int st=1,dr=n,mid,sol=-1,sum;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        sum=Sum(mid);
        if(sum==x)
        {
            dr=mid-1;
            sol=mid;
        }
        else if(sum>x)
        {
            dr=mid-1;
        }
        else
        {
            st=mid+1;
        }
    }
    return sol;
}
int main()
{
    int i,pstart,pstop,j,x;
    cin>>n;
    for(i=1; i<=n; i++)
    {
        Add(i,1);
    }
    pstart=1;
    for(i=1; i<=n; i++)
    {
        pstop=(Sum(pstart)+i)%(n-i+1);/// numarul cu pozitia pe care trebuie sa il caut sa obtin pstop
        if(pstop==0) pstop=n-i+1;
        x=Caut_Bin(pstop);
        cout<<x<<" ";
        Add(x,-1);
        if(Sum(x)==0)
            pstart=Caut_Bin(Sum(n));
        else
            pstart=Caut_Bin(pstop-1);
    }
    //cout<<Caut_Bin(1);
    return 0;
}