Cod sursa(job #2777096)

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

template <class T_Data, class T_Over>
class FenwickTree{
public:
    vector<T_Data> data;

    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 < data.size())
        {
            data[i] += delta;
            i += (i & (-i));
        }
    }

    FenwickTree(int capacity) : data(capacity + 1, 0){}
};

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));
    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;
}