Cod sursa(job #1349321)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 20 februarie 2015 09:15:34
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
using namespace std;

ifstream f("order.in");
ofstream g("order.out");

int n;
#define N 30005
int a[N],q=1;
int m,nr,ps=1;
void update(int pos ,int val){
    for(;pos<=n;pos+=pos&-pos) a[pos]+=val;
}

int bfs(int sum){
    int sol = 0, p=1;
    for( ; p <=n; p<<=1 );
    for( ; p    ; p>>=1 ){
        if( sol + p <= n && a[sol+p] <= sum ){
            sol +=p;
            sum -= a[sol];
        }
    }
    return sol;
}



int main()
{
    f >> n;
    for(int i=1;i<=n;++i) update(i,1);
    nr = n;
    for(int i=1;i<=n;++i){
        m = (ps+q) %nr;
       //if(  )
        m = bfs(m);
        g << m << " ";
        update(m,-1);
       --nr;
        ps+=i;
        q= m;
    }


    return 0;
}