Cod sursa(job #1956359)

Utilizator the.manIon Man the.man Data 6 aprilie 2017 18:04:56
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
using namespace std;
ifstream fi("order.in");
ofstream fo("order.out");
int n, a[30001];

void Update(int x,int v)
{
    for (int i=x; i <= n; i += i&-i)
        a[i]+=v;
}
int Query(int x)
{
    int s = 0;
    for (int i=x ; i>=1; i -=i&-i) s += a[i];
    return s;
}

int Search(int x)
{
    int st=1,dr=n,mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        int nr=Query(mij);
        if (nr==x) return mij;
        if (nr<x) st=mij+1;
             else dr=mij-1;
    }
}

int main()
{
fi >> n;

for (int i=1;i<= n;i++) Update(i,1);

for (int i=1,x=2; i<= n;i++)
    {
        x = (x - 1 + i) % (n - i + 1);
        if (x == 0) x = n - i + 1;

        int poz=Search(x);
        Update(poz,-1);
        fo << poz << " ";
    }
}