Cod sursa(job #1700570)

Utilizator Bodo171Bogdan Pop Bodo171 Data 10 mai 2016 20:07:48
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include<fstream>
using namespace std;
int aib[30005],i,j,n,aux,actual,poz,p,u,m,key;
inline int lbit(int x)
{
    return((x^(x-1))&x);
}
void update(int x,int val)
{
    for(j=x;j<=n;j+=lbit(j))
        aib[j]+=val;
}
int compute(int x)
{
    int sum=0;
    for(j=x;j>0;j-=lbit(j))
        sum+=aib[j];
    return sum;
}
int searchandconquer(int x)
{
    p=0;u=n+1;
    while(u-p>1)
    {
        m=(p+u)/2;
        key=compute(m);
        if(key<x) p=m;
        else u=m;
    }
    return u;
}
int main()
{
    ifstream f("order.in");
    ofstream g("order.out");
    f>>n;
    aib[n+1]=(1<<30);
    for(i=1;i<=n;i++) update(i,1);
    actual=1;
    for(i=1;i<=n;i++)
    {
        aux=compute(actual);
        if(i<=(n-i+1)-aux) poz=aux+i;
        else poz=(i+aux)%(n-i+1);
        if(poz==0) poz=n-i+1;
        actual=searchandconquer(poz);
        cout<<actual<<'\n';
        update(actual,-1);
        g<<actual<<' ';
    }
    return 0;
}