Cod sursa(job #145811)

Utilizator scvalexAlexandru Scvortov scvalex Data 29 februarie 2008 15:28:40
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

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;
};

int N;
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 main(int argc, char *argv[]) {
	ifstream fin("order.in");
	fin >> N;
	fin.close();

	buildList();

	listCut();

	return 0;
}