Cod sursa(job #1357514)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 23 februarie 2015 22:43:26
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#define ub(i) i&(-i)
#define nmax 30005
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int aib[nmax],v[nmax];
int n,m,ps=2,si;
char s[nmax*10];

int query(int poz)
{

    int sol=0,i;
    for(i=poz;i>=1;i-=ub(i))
        sol+=aib[i];
    return sol;
}
void write()
{
    int i,x;
    int k[10]={0},nrk=0;

    for (i=1;i<=n;i++) {
        x=v[i];
        while (x) {
            k[++nrk]=x%10;
            x/=10;
        }
        while (nrk) {
            s[si++]=k[nrk--]+'0';
        }
        if (i!=n)
            s[si++]=' ';
    }
    g<<s;


}

void update(int poz,int x)
{
    int i;
    for (i=poz;i<=n;i+=ub(i))
            aib[i]+=x;
}

int main()
{
    int i,nr;
    f>>n;
    for (i=1;i<=n;i++) update(i,1);
    nr=n;
    for(i=1;i<=n;i++){
        --nr;
        int sol=0;
        for(int p=1<<14;p;p>>=1){
            if(sol+p<=n&&query(sol+p)<ps)
                sol +=p;
        }

        ++sol;
        v[i]=sol;
        update(sol,-1);
        ps+=i;
        if( nr ) ps%=nr;
        if(!ps ) ps = nr;
    }

    write();
    return 0;
}