Cod sursa(job #2942035)

Utilizator rastervcrastervc rastervc Data 18 noiembrie 2022 20:01:43
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <iostream>

using namespace std;

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

#define stinl static inline
constexpr int MAX_N = 30005;

stinl void wrap(int& i, int N) {
	i %= N;
	if (i == 0) i = N;
}

namespace BIT {
	int tree[MAX_N], N;

	stinl void add(int i, int x) {
		for (; i <= N; i += i & (-i))
			tree[i] += x;
	}

	stinl int prefix(int i) {
		int sum = 0;
		for (; i > 0; i -= i & (-i))
			sum += tree[i];
		return sum;
	}

	stinl int segment(int i1, int i2) {
		int cnt = (i2 - 1) / N;
		wrap(i2, N);
		return cnt * prefix(N) - prefix(i1 - 1) + prefix(i2);
	}

	stinl void init(int N) {
		BIT::N = N;
		for (int i = 1; i <= N; i++)
			add(i, 1);
	}
}

int N, i, pos, low, high, mid, sol, sum;

int main() {
	fin >> N;
	BIT::init(N);

	pos = 1;
	for (i = 1; i <= N; i++) {
		low = pos + 1, high = pos + 1, sol = -1;
		
		while (BIT::segment(pos + 1, high) <= i)
			high *= 2;

		while (low <= high) {
			mid = (low + high) / 2;
			sum = BIT::segment(pos + 1, mid);

			if (sum >= i) {
				sol = mid;
				high = mid - 1;
			}
			else low = mid + 1;
		}

		pos = sol;
		wrap(pos, N);
		BIT::add(pos, -1);
		fout << pos << ' ';
	}

	fin.close();
	fout.close();
	return 0;
}