Cod sursa(job #2777104)

Utilizator 23liviuStanescu Liviu 23liviu Data 22 septembrie 2021 09:47:49
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <vector>
using namespace std;

template <class T_Data, class T_Over>
class FenwickTree{
public:
    T_Data* data;
    int len;

    T_Over GetSum(int i)
    {
        T_Over sum = 0;
        ++i;
        while(i > 0)
        {
            sum += data[i];
            i -= (i & (-i));
        }
        return sum;
    }

    void Add(int i, T_Data delta)
    {
        ++i;
        while(i < len)
        {
            data[i] += delta;
            i += (i & (-i));
        }
    }

    FenwickTree(int capacity)
    {
    	data = (T_Data*) calloc(capacity + 1, sizeof(T_Data));
    	len = capacity + 1;
    }
};

int binary(int n, int target, FenwickTree<int,int> aib)
{
	int mid, st, dr, out;
	st = 1;
	dr = out = n;
	while(st <= dr)
	{
		mid = (st + dr) / 2;
		if(aib.GetSum(mid) <= target)
		{
			st = mid + 1;
			out = mid;
		}
		else
			dr = mid - 1;
	}
	return out;
}

int main()
{
	ifstream cin ("order.in");
	ofstream cout("order.out");

    int n, it;
    cin >> n;
    FenwickTree<int,int> aib = *(new FenwickTree<int,int>(n+1));
    for(int i = 1; i <= n; i++)
		aib.Add(i, 1);
    int pos = 2;
    for(int i = 1; i <= n; i++)
	{
		pos = (pos + i - 1) % (n - i + 1);
		if(pos == 0)
			pos = n - i + 1;

		for(it = binary(n, pos, aib); aib.GetSum(it) == pos; it--)
			;
		aib.Add(it + 1, -1);
        cout << it + 1 << " ";
	}
    return 0;
}