Cod sursa(job #2876008)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 22 martie 2022 20:28:47
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>

using namespace std;


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

int n;
struct aint
{
    int size;
    vector <int> values;

    int merge(int a, int b)
    {
        return a + b;
    }

    int single(int v)
    {
        return v;
    }

    void init(int n)
    {
        size = 1;
        while(size < n)
            size *= 2;
        values.resize(2 * size);
    }

    void build(int x, int l, int r)
    {
        if( r == l)
        {
            values[x] = 1;
            return ;
        }
        int m = (l + r) / 2;
        build(2 * x, l, m);
        build(2 * x + 1, m + 1, r);
        values[x] = merge(values[2 * x], values[2 * x + 1]);
    }


    void set(int v, int node, int l, int r)
    {
        if(r == l)
        {
            values[node] = 0;
            out << l << " ";
            return;
        }
        int m = (l + r) / 2;
        if(v <= values[2 * node])
            set(v, 2 * node, l, m);
        else
            set(v - values[node * 2], 2 * node + 1, m + 1, r);
        values[node] = merge(values[2*node], values[2*node + 1]);
    }

    void set(int v)
    {
        set(v, 1, 1, n);
    }
};

int main()
{

    in >> n;
    aint t;
    t.init(n);
    t.build(1, 1, n);
    int libere = n, last = 2;
    for(int i = 1; i <= n; i++)
    {
        last = (i + last - 1) % libere;
        if(last == 0)
            last = libere;
        t.set(last);
        libere--;
    }
    return 0;
}