Cod sursa(job #2903041)

Utilizator andriciucandreeaAndriciuc Andreea andriciucandreea Data 17 mai 2022 01:32:58
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>	
#include <fstream>	
#include <vector>
		
using namespace std;
	
ifstream fin ("order.in");	
ofstream fout("order.out");

vector <int> v(4*300005, 1);

void construct(int pos, int left, int right)
{
    if(left == right)
    {
        v[pos] = 1;
        return;
    }
    int mid = (left + right) / 2;
    construct(pos*2, left, mid);
    construct(pos*2+1, mid+1, right);
    v[pos] = v[pos * 2] + v[pos * 2 + 1];
}

void update(int curr, int left, int right, int x)
{
    if(left == right)
    {
        v[curr] = 0;
        return;
    }
    int mid = (left + right) / 2;
	if (x <= mid)
		update(2 * curr, left, mid, x);
	else
		update(2 * curr + 1, mid + 1, right, x);
	v[curr] = v[2 * curr] + v[2 * curr + 1];
}

int search(int curr, int left, int right, int pos)
{
    if(left == right)
        return left;
    if(v[2*curr] < pos)
        return search(curr * 2 + 1, (left + right) / 2 + 1, right, pos - v[curr * 2]);
    return search(curr * 2, left, (left + right) / 2, pos);
}

int main()	
{
    int i, n, pos = 2, elem;
	fin>>n;
    construct(1, 1, n);
    for(int i = 1; i <= n; i++)
    {
        pos += i;
        pos --;
        while(pos > v[1])
            pos -= v[1];
        elem = search(1, 1, n, pos);
        update(1, 1, n, elem);
        fout<<elem<<' ';

    }
    return 0;
	
}