Cod sursa(job #1595934)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 10 februarie 2016 17:26:43
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>

using namespace std;
const int NMAX=30005;
int aib[NMAX], sol[NMAX], n;
void update(int pos, int val)
{
    for(; pos<=n; pos+=pos&(-pos))
        aib[pos]+=val;
}
int query(int pos)
{
    int sum=0;
    for(; pos; pos-=pos&(-pos))
        sum+=aib[pos];
    return sum;
}
int bs(int x)
{
    int l=1, r=n, mid;
    int minim=(1<<30);
    while (l<=r)
    {
        mid=(l+r)/2;
        if (query(mid)==x && mid<minim)
            minim=mid;
        if (query(mid)<x)
            l=mid+1;
        else r=mid-1;
    }
    return minim;
}
int main()
{
    ifstream in("order.in");
    ofstream out("order.out");
    int x, pos, k, ind, i;
    in>>n;
    for(i=1; i<=n; i++)
        update(i, 1);

    ind=n;
    k=2;
    for(i=1; i<=n; i++)
    {
        ind--;
        pos=bs(k);
        update(pos, -1);
        sol[i]=pos;
        k+=i;
        if(ind)
        {
            if(k%ind==0)
                k=ind;
            else
                k=k%ind;
        }

    }
    for(i=1; i<=n; i++)
        out<<sol[i]<<' ';
    return 0;
}