Cod sursa(job #2902992)

Utilizator andriciucandreeaAndriciuc Andreea andriciucandreea Data 17 mai 2022 00:31:13
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>	
#include <fstream>	
#include <vector>
		
using namespace std;
	
ifstream fin ("order.in");	
ofstream fout("order.out");
	
int n;
vector <int> v(4*300005, 1);

void construct(int pos, int left, int right)
{
    if(left == right)
    {
        v[pos] = 1;
        return;
    }
    v[n] = right - left + 1;
    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 pos, int x)
{
    if(pos < left || pos > right) return;
    if(left == right)
    {
        v[curr] = x;
        return;
    }
    update(curr * 2, left, (left + right) / 2, pos, x);
    update(curr * 2 + 1, (left + right) / 2 + 1, right, pos, x);
    v[curr] = v[curr * 2] + v[curr * 2 + 1];
}

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

int main()	
{
	fin>>n;
    int left = n, pos = 2;
    construct(1, 1, n);
    for(int i = 1; i <= n; i++)
    {
        pos = (i+pos-1)%left;
        if(pos==0) pos==left;
        left--;
        int x = solve(1, 1, n, pos);
        update(1, 1, n, x, 0);

    }
    return 0;
	
}