Cod sursa(job #2019674)

Utilizator stefantagaTaga Stefan stefantaga Data 8 septembrie 2017 12:16:35
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <climits>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int ub(int i)
{
    return (i&(-i));
}
int aib[30001];
int n;
void upgrade(int poz,int val)
{
    int i;
    for (i=poz;i<=n;i=i+ub(i))
    {
        aib[i]+=val;
    }
}
int sum(int poz)
{
    int i,s=0;
    for (i=poz;i>0;i-=ub(i))
    {
        s+=aib[i];
    }
    return s;
}
int cautarebinara(int x)
{
    int st=1,dr=n,minim=INT_MAX,mijl,t;
    while (st<=dr)
    {
        mijl=(st+dr)/2;
        t=sum(mijl);
        if(t==x&&mijl<minim)minim=mijl;
        else if (t<x)st=mijl+1;
             else dr=mijl-1;
    }
    return minim;
}
int ramas,k,x;
int main()
{
    int i,poz;
    f>>n;
    ramas=n;
    k=1;
    for (i=1;i<=n;i++)
    {
        upgrade(i,1);
    }
    ramas=n;
    poz=2;
    for (i=1;i<=n;i++)
    {
        int x=cautarebinara(poz);
        upgrade(x,-1);
        g<<x<<" ";
        ramas--;
        poz+=i;
        if (ramas)
        {
            if (poz%ramas==0)
            {
                poz=ramas;
            }
            else
            {
                poz=poz%ramas;
            }
        }
    }
    g<<'\n';
    return 0;
}