Cod sursa(job #1241213)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 12 octombrie 2014 23:09:00
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <fstream>

using namespace std;

#define nmax 30005

ifstream fin("order.in");
ofstream fout("order.out");

int n, i;
int currentSize, poz, x, currentSpot;
int ARB[4*nmax+1];

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

int query(int nod, int st, int dr, int poz)
{
    
    ARB[nod]--;
    
    if (st == dr)
        return st;
    
    int mid = (st + dr) >> 1;
    
    if (ARB[2*nod] >= poz) return query(2*nod, st, mid, poz);
    else                   return query(2*nod+1, mid+1, dr, poz - ARB[2*nod]);
    
}

void solve()
{
    fin >> n;
    build(1, 1, n);
    
    currentSpot = 2;
    
    for (i=1; i<=n; i++)
    {
        currentSize = ARB[1];
        
        x = (currentSpot + i - 1) % currentSize;
        
        if (x == 0) x = currentSize;
        
        currentSpot = x;
        
        fout << query(1, 1, n, x) << " ";
    }
}

int main()
{
    
    solve();
    
    fin.close();
    fout.close();
    
    return 0;
}