Cod sursa(job #1035368)

Utilizator george_stelianChichirim George george_stelian Data 18 noiembrie 2013 15:14:52
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>

using namespace std;

int v[100000],n,i,poz,val,k,sol;

void schimba(int nod,int st,int dr)
{
    if(st==dr)
    {
        v[nod]=val;
        return;
    }
    int mid=(st+dr)/2;
    if(poz<=mid) schimba(nod*2,st,mid);
    else schimba(nod*2+1,mid+1,dr);
    v[nod]=v[nod*2]+v[nod*2+1];
}

void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        v[nod]=1;
        return;
    }
    int mid=(st+dr)/2;
    build(nod*2,st,mid);
    build(nod*2+1,mid+1,dr);
    v[nod]=v[nod*2]+v[nod*2+1];
}

void raspunde(int nod,int st,int dr,int x)
{
    if(st==dr)
    {
        sol=st;
        return;
    }
    int mid=(st+dr)/2;
    if(v[nod*2]>=x) raspunde(nod*2,st,mid,x);
    else raspunde(nod*2+1,mid+1,dr,x-v[nod*2]);
}

int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    scanf("%d",&n);
    build(1,1,n);
    k=2;
    for(i=1;i<=n;i++)
    {
        k=(k+i-1)%v[1];
        if(k==0) k=v[1];
        raspunde(1,1,n,k);
        printf("%d ",sol);
        poz=sol;val=0;
        schimba(1,1,n);
    }

    fclose(stdin);fclose(stdout);
    return 0;
}