Cod sursa(job #147817)

Utilizator scvalexAlexandru Scvortov scvalex Data 3 martie 2008 16:49:53
Problema Order Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

int N;

/*class Node {
public:
	Node(int _n) :
		n(_n),
		next(0)
	{
	}

	int n;
	Node *next;
};

class Group {
public:
	Group() :
		firstChild(-1),
		next(0),
		count(0)
	{
	}

	Node firstChild;
	Group *next;
	int count;
};

Group groups;

void buildList() {
	int gs = sqrt(N);
	Group *cur = &groups;
	int k(0);
	for (int i(0); i <= gs; ++i) {
		if (k == N)
			break;
		cur->next = new Group();
		cur = cur->next;
		Node *curn = &cur->firstChild;
		for (int j = i * gs; (j <= (i + 1) * gs) && (k < N); ++j, ++k) {
			curn->next = new Node(k + 1);
			curn = curn->next;
			++cur->count;
		}
	}
	cur->next = groups.next;

//	cur = groups.next;
//	while (cur) {
	//	cout << cur->count << ": ";
	//	Node *curn = cur->firstChild.next;
	//	while (curn) {
	//		cout << curn->n << " ";
	//		curn = curn->next;
	//	}
	//	cout << endl;
	//	cur = cur->next;
	//}
}

void listCut() {
	FILE *fout = fopen("order.out", "w");

	Group *curg = groups.next;
	Node *curn = curg->firstChild.next;
	int indgroup(0);

	int cut(0);
	int skip(1);
	while (cut < N) {
		int nows = indgroup + skip++;
		//cout << "nows: " << nows << endl;
		while (nows >= curg->count) {
			//cout << "Skipping group..." << endl;
			nows -= curg->count;
			curg = curg->next;
		}

		indgroup = nows;
		curn = &(curg->firstChild);
		Node *p;
		for (int i(0); i <= indgroup; ++i) {
			p = curn;
			curn = curn->next;
		}

		p->next = curn->next;
		--curg->count;
		fprintf(fout, "%d ", curn->n);
		--indgroup;

		++cut;
	}
	fprintf(fout, "\n");
	fclose(fout);
}*/

int T[64000];
int build_tree(int st, int dr, int cur) {
	if (st == dr)
		return T[cur] = 1;

	int q = (st + dr) / 2;
	T[cur] = build_tree(st, q, cur*2) +
			 build_tree(q + 1, dr, cur*2+1);

	return T[cur];
}

int find_and_cut_nth(int n, int st, int dr, int cur) {
	//cout << st << "-" << dr << endl;
	--T[cur];
	if (st == dr)
		return st;

	int q = (st + dr) / 2;

	int b;
	if (n > T[cur*2])
		b = find_and_cut_nth(n - T[cur*2], q + 1, dr, cur*2+1);
	else
		b = find_and_cut_nth(n, st, q, cur*2);

	return b;
}

void print_tree(int st, int dr, int cur = 1, int d = 0) {
	if (!T[cur])
		return;
	
	for (int i(0); i < d; ++i)
		cout << "  ";
	cout << st << " - " << dr << ":\t\t" << T[cur] << endl; 

	print_tree(st, (st+dr)/2, cur*2, d+1);
	print_tree((st+dr)/2+1, dr, cur*2+1, d+1);
}

void chop_it() {
	int cur = 2;
	int skip = 1;

	FILE *fo = fopen("order.out", "w");
	while (T[1]) {
		fprintf(fo, "%d ", find_and_cut_nth(cur, 1, N, 1));

		if (T[1]) {
			cur = (cur + skip) % T[1];
			if (!cur)
				cur = T[1];
		}
	
		++skip;
	}
	fprintf(fo, "\n");
	fclose(fo);
}

int main(int argc, char *argv[]) {
	ifstream fin("order.in");
	fin >> N;
	fin.close();

	//buildList();
	//listCut();

	build_tree(1, N, 1);

	chop_it();

	return 0;
}