Cod sursa(job #2913467)

Utilizator lolismekAlex Jerpelea lolismek Data 14 iulie 2022 17:35:08
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 3e5;
int seg[4 * N + 1];

void update(int nod, int st, int dr, int poz, int val){
	if(st == dr){
		seg[nod] += val;
		return;
	}

	int mij = (st + dr) / 2;
	if(poz <= mij)
		update(2 * nod, st, mij, poz, val);
	else
		update(2 * nod + 1, mij + 1, dr, poz, val);

	seg[nod] = seg[2 * nod] + seg[2 * nod + 1];
}

int query(int nod, int st, int dr, int l, int aux){
	if(st == dr)
		return st;

	int mij = (st + dr) / 2;
	if(mij - st + 1 - seg[2 * nod] + aux > l)
		return query(2 * nod, st, mij, l, aux);
	else
		return query(2 * nod + 1, mij + 1, dr, l, aux + mij - st + 1 - seg[2 * nod]);
}

int main(){

	int n, l = 1;
	fin >> n;

	for(int i = 1; i <= n; i++){
		l = (l + i - 1) % (n - i + 1);

		int p = query(1, 1, n, l, 0);
		update(1, 1, n, p, 1);

		fout << p << ' ';
	}

	return 0;
}