Cod sursa(job #2592325)

Utilizator StanCatalinStanCatalin StanCatalin Data 1 aprilie 2020 16:16:40
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int dim = 30005;

int n,arb[4*dim];

void Update(int nod,int st,int dr,int pos,int val)
{
    if (st == dr)
    {
        arb[nod] = val;
        return ;
    }
    int mid = (st+dr)/2;
    if (pos <= mid) Update(2*nod,st,mid, pos,val);
    else Update(2*nod+1,mid+1,dr,pos,val);
    arb[nod] = arb[2*nod] + arb[2*nod+1];
}

int Querry(int nod,int st,int dr,int suma)
{
    if (st == dr)
    {
        return st;
    }
    int mid = (st+dr)/2;
    int suma_stanga = arb[2*nod];
    if (suma > suma_stanga)
    {
        return Querry(2*nod+1,mid+1,dr,suma - suma_stanga);
    }
    else
    {
        return Querry(2*nod,st,mid,suma);
    }
}

int main()
{
    in >> n;
    for (int i=1; i<=n; i++)
    {
        Update(1,1,n,i,1);
    }
    int poz = 1;
    int ramase = n;
    for (int i=1; i<=n; i++)
    {
        poz = (poz + i)%ramase;
        if (poz == 0) poz = ramase;
        int po = Querry(1,1,n,poz);
        out << po << " ";
        Update(1,1,n,po,0);
        poz--;
        ramase--;
    }
    return 0;
}