Cod sursa(job #2777077)

Utilizator cezar_titianuTitianu Cezar cezar_titianu Data 22 septembrie 2021 09:00:04
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <vector>

std::vector <int> aib;

void update(int pos) {
	while (pos < aib.size()) {
		aib[pos]--;
		pos += (pos & -pos);
	}
}

int query(int pos) {
	int ans = 0;
	while (pos) {
		ans += aib[pos];
		pos &= (pos - 1);
	}
	return ans;
}

int main() {
	std::ifstream fin("order.in");
	std::ofstream fout("order.out");
	int nrn;
	int pos;
	int pos1, pos2, mid;
	fin >> nrn;
	for (int index = 0; index <= nrn; index++) {
		aib.push_back(index & -index);
	}
	pos = 1;
	for (int index = 0; index < nrn; index++) {
		pos += index;
		pos %= nrn - index;
		pos++;
		pos1 = 0;
		pos2 = nrn;
		while (pos2 - pos1 > 1) {
			mid = (pos1 + pos2) / 2;
			if (query(mid) < pos) {
				pos1 = mid;
			}
			else {
				pos2 = mid;
			}
		}
		fout << pos2 << ' ';
		update(pos2);
		pos--;
	}
}