Cod sursa(job #2442188)

Utilizator TheNextGenerationAyy LMAO TheNextGeneration Data 23 iulie 2019 10:35:20
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("order.in");
ofstream out("order.out");
const int N = 30000;
int tree[4*N];

void update(int node, int st, int dr, int poz)
{
    if (st == dr)
    {
         tree[node]++;
         return;
    }
    int mj = (st + dr)/2;
    if (poz <= mj)
        update(2*node, st, mj, poz);
    else
        update(2*node+1, mj+1, dr, poz);
    tree[node] = tree[2*node] + tree[2*node+1];
}

int search(int node, int st, int dr, int next)
{
    tree[node]--;
    if (st == dr)
        return st;
    int mj = (st + dr)/2;
    if (next <= tree[2*node])
        return search(2*node, st, mj, next);
    else
        return search(2*node+1, mj+1, dr, next - tree[2*node]);
}

int query(int node, int st, int dr, int poz)
{
    if (st == dr)
        return tree[node];
    int mj = (st + dr)/2;
    if (poz <= mj)
        return query(2*node, st, mj, poz);
    else
        return tree[2*node] + query(2*node+1, mj+1, dr, poz);
}

int main()
{
    int n,next,x;
    in >> n;
    for (int i = 1; i <= n; i++)
        update(1,1,n,i);
    x = search(1, 1, n, 2);
    out << x << " ";
    for (int i = 2; i <= n; i++)
    {
        next = (query(1, 1, n, x)+i-1)%tree[1]+1;
        x = search(1, 1, n, next);
        out << x << " ";
    }
    return 0;
}