Cod sursa(job #2451464)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 26 august 2019 20:20:42
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("farfurii.in");
ofstream fout("farfurii.out");

const int DIM = 1e5 + 7;

int arb[DIM * 4];

void build(int pos, int l, int r)
{
	arb[pos] = r - l + 1;
	
	if(l != r)
	{
		int mid = (l + r) / 2;
		
		build(pos * 2, l, mid);
		build(pos * 2 + 1, mid + 1, r);
	}
}

void update(int pos, int l, int r, int x)
{
	if(l == r)
	{
		arb[pos] = 0;
		return ;
	}
	
	int mid = (l + r) / 2;
	
	if(x <= mid)
		update(pos * 2, l, mid, x);
	
	if(x > mid)
		update(pos * 2 + 1, mid + 1, r, x);
	
	arb[pos] = arb[pos * 2] + arb[pos * 2 + 1];
}

int query(int pos, int l, int r, int x)
{
	if(l == r)
	{
		return l;
	}
	
	int mid = (l + r) / 2;
	
	if(arb[pos * 2] >= x)
		return query(pos * 2, l, mid, x);
	else
		return query(pos * 2 + 1, mid + 1, r, x - arb[pos * 2]);
}

main()
{
	int n;
	long long m;
	fin >> n >> m;
	
	build(1, 1, n);
	
	for(int i = 1; i <= n; i++)
	{
		int p = n - i;
		
		if(p * 1LL * (p - 1) / 2 >= m)
		{
			int pos = query(1, 1, n, 1);
			
			update(1, 1, n, pos);
			
			fout << pos << ' ';
		}
		else
		{
			int t = m - p * 1LL * (p - 1) / 2 + 1;
			int pos = query(1, 1, n, t);
			
			m = p * 1LL * (p - 1) / 2;
			
			update(1, 1, n, pos);
			
			fout << pos << ' ';
		}
	}
}