Cod sursa(job #254581)

Utilizator CezarMocanCezar Mocan CezarMocan Data 7 februarie 2009 13:03:13
Problema Planeta Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 2 Marime 1.84 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int v[20], i, j, arb[40000], n, p, nsol, ret;
vector <int> sol[30000];

void pre_order(int nod, int nsol) {
	sol[nsol].push_back(arb[nod]);
	if (arb[2 * nod])
		pre_order(2 * nod, nsol);
	if (arb[2 * nod + 1])
		pre_order(2 * nod + 1, nsol);
}

void solve(int nsol) {
	int i, j, nod;
	for (i = 1; i <= n; i++) {
		//tre sa baqg numaru i in arborele binar de cautare
		nod = 1;
		while (arb[nod] != 0) {
			if (v[i] < arb[nod])
				nod *= 2;
			else
				nod = nod * 2 + 1;
		}
		arb[nod] = v[i];
	}
	
	pre_order(1, nsol);
	
}

void back(int k) {
	int i, j, ok;
	if (k == n) {
		nsol++;
		memset(arb, 0, sizeof(arb));
		solve(nsol);
		if (n > 7 && nsol > p + 1000) {
			ret = 1;
			return;
		}
	}
	else {
		if (ret == 1)
			return;
		for (i = 1; i <= n; i++) {
			ok = 1;
			for (j = 1; j <= k; j++)
				if (v[j] == i) {
					ok = 0;
					break;
				}
			if (ok) {
				v[k + 1] = i;
				back(k + 1);
			}
		}
	}
	
	
}

void back2(int k) {
	int i, j, ok;
	if (k == n) {
		for (i = 1; i <= n; i++)
			printf("%d ", v[i]);
		printf("\n");
	}
	else {
		for (i = 1; i <= n; i++) {
			ok = 1;
			for (j = 1; j <= k; j++)
				if (v[j] == i) {
					ok = 0;
					break;
				}
			if (ok) {
				v[k + 1] = i;
				back2(k + 1);
			}
		}
	}
}


int main() {
	freopen("planeta.in", "r", stdin);
	freopen("planeta.out", "w", stdout);
	
	scanf("%d%d", &n, &p);
	
	back(0);
	
	sort(sol + 1, sol + nsol + 1);
	
/*	for (i = 1; i <= nsol; i++) {
//		if (sol[i] != sol[i - 1]) {
			for (j = 0; j < sol[i].size(); j++)
				printf("%d ", sol[i][j]);
			printf("\n");
	/*	}
		else {
			printf("%d\n", i);
		}
	}*/
	
	for (j = 0; j < sol[p].size(); j++)
		printf("%d ", sol[p][j]);
	printf("\n");
	
	return 0;
}