Cod sursa(job #2549208)

Utilizator LivcristiTerebes Liviu Livcristi Data 17 februarie 2020 13:55:26
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
#define NUM 30005
int arb[NUM * 4];
int v[NUM];
int n, poz, val, N, p = 2, r;
using namespace std;
ifstream f("order.in");
ofstream g("order.out");

void update(int nod, int st, int dr)
{
    if(st == dr)
    {
        arb[nod] = val;
        return;
    }
    int mij = st + (dr - st) / 2;
    if(poz <= mij)
        update(2 * nod, st, mij);
    else
        update(2 * nod + 1, mij + 1, dr);
    arb[nod] = arb[2 * nod] + arb[2 * nod + 1];
}

void query(int nod, int st, int dr, int val)
{
    if(st == dr)
    {
        r = st;
        return;
    }
    int mij = st + (dr - st) / 2;
    if(arb[2 * nod] >= val)
        query(2 * nod, st, mij, val);
    else
        query(2 * nod + 1, mij + 1, dr, val - arb[2 * nod]);
}

int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
    {
        poz = i;
        val = 1;
        v[i] = i;
        update(1, 1, n);
    }
    N = n;
    for(int i = 1; i <= n; ++i)
    {
        p = (p % N == 0) ? N : (p % N);
        query(1, 1, n, p);
        g << r << ' ';
        poz = r;
        val = 0;
        update(1, 1, n);
        p += i;
        N--;
    }
    f.close();
    g.close();
}