Cod sursa(job #2013841)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 22 august 2017 15:09:24
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
//Se foloseste stiva S pt a retine elementele care vor trebui eliminate
#include<fstream>
#include<stack>
using namespace std;
ifstream fi("order.in");
ofstream fo("order.out");
int n,i,ind,poz,ramas,F[30001];
stack<int> S;

void update(int poz, int val)
{
    while(poz<=n)
    {
        F[poz]+=val;
        poz=poz+(poz&(poz^(poz-1)));
    }
}

int f(int poz)
{
    int rez=0;
    while(poz>0)
    {
        rez+=F[poz];
        poz=poz-(poz&(poz^(poz-1)));
    }
    return rez;
}

int query(int st, int dr)
{
    return f(dr)-f(st-1);
}

int bs(int val)
{
    int st=1,dr=n,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        int k=query(1,mij);
        if(val<=k)
        {
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    return st;
}

int main()
{
    fi>>n;
    ramas=n;
    ind=1;
    for(i=1; i<=n; i++)
        update(i,1);
    for(i=1; i<=n; i++)
    {
        ind=ind+i;
        if(ind>ramas)
        {
            ind=ind-ramas;
            while(!S.empty())
            {
                update(S.top(),-1);
                S.pop();
                ramas--;
            }
            ind=ind%ramas;
            if(ind==0)
                ind=ramas;
        }
        poz=bs(ind);
        fo<<poz<<" ";
        S.push(poz);
        //update(poz,-1);
    }
    fo<<"\n";
    fi.close();
    fo.close();
    return 0;
}