Cod sursa(job #1602581)

Utilizator andreimdvMoldovan Andrei andreimdv Data 16 februarie 2016 20:30:01
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
//arbor de intervale, cu suma pe intervalele respective
#include <fstream>
#include<iostream>
using namespace std;

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

int n,i,sol,nrc,nrr,Arb[30000*5];

void Update(int nod,int pos,int val,int left,int right)
{
    //nod, left si right pentru parcurgere in jos
    //valoare de pe pozitia pos (din vector) devine val;
    if(left==right)
    {
        Arb[nod]=val; // practic v[pos]=val;
        return ;
    }
    int mij=(left+right)/2;
    if(pos<=mij) Update(nod*2,pos,val,left,mij);
    else        Update(nod*2+1,pos,val,mij+1,right);

    Arb[nod]=Arb[nod*2]+Arb[nod*2+1];
}

void Query(int nod,int alcateleaelement, int left, int right)
{
    //un query putin diferit de arborii originali, deoarece arborele retine sume
    if(left==right)
    {
        sol= left;
        return ;
    }
    int mij=(left+right)/2;
    if(alcateleaelement>Arb[nod*2]) Query(nod*2+1,alcateleaelement-Arb[nod*2],mij+1,right);
    else                            Query(nod*2,alcateleaelement,left,mij);
}

int main()
{
    fin>>n;
    for(i=1;i<=n;++i)
    {
        Update(1,i,1,1,n);
    }
    nrc=1;
    nrr=n;
    for(i=1;i<=n;++i)
    {

        nrc=(nrc+i)%nrr;
        //cout<<nrc<<" ";
        if(nrc==0)
            nrc=nrr;
        Query(1,nrc,1,n) ;
        Update(1,sol,0,1,n);
        fout<<sol<<" ";
        nrc--;
        nrr--;
    }

    return 0;
}