Cod sursa(job #2427243)

Utilizator copanelTudor Roman copanel Data 31 mai 2019 12:15:27
Problema Order Scor 100
Compilator c-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>

int arb[131073];

int query(int st, int dr, int p, int node) {
	if (st == dr) {
		arb[node] = 1;
		return st;
	}
	int m = (st + dr) / 2;
	int ramase = m - st + 1 - arb[2 * node], r;
	if (ramase >= p) {
		r = query(st, m, p, 2 * node);
	} else {
		r = query(m + 1, dr, p - ramase, 2 * node + 1);
	}
	arb[node] = arb[2 * node] + arb[2 * node + 1];
	return r;
}

int main() {
	FILE *fin = fopen("order.in", "r"),
	     *fout = fopen("order.out", "w");
	int n, i, pos;

	fscanf(fin, "%d", &n);
	fclose(fin);

	pos = 2;
	for (i = 1; i <= n; i++) {
		fprintf(fout, "%d ", query(1, n, pos, 1));
		/* n - arb[1] = numarul de copii ramasi */
		if (n - arb[1] > 0) {
			pos = (pos + i) % (n - arb[1]);
			if (pos == 0) {
				pos = n - arb[1];
			}
		}
	}
	fclose(fout);
	return 0;
}