Cod sursa(job #1035347)

Utilizator george_stelianChichirim George george_stelian Data 18 noiembrie 2013 15:07:06
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>

using namespace std;

int v[100000],n,i,poz,val,j,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);
    i=1;
    j=1;
    k=n;
    while(k)
    {
        j+=i;
        j%=k;
        if(j!=1) j--;
        if(j==-1) j=k-1;
        if(j==0) j=k;
        raspunde(1,1,n,j);
        poz=sol;val=0;
        schimba(1,1,n);
        printf("%d ",sol);
        i++;
        k--;
    }
    fclose(stdin);fclose(stdout);
    return 0;
}