Cod sursa(job #166964)

Utilizator victorsbVictor Rusu victorsb Data 28 martie 2008 19:07:41
Problema Sortare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define Nmax 5015
#define INF 0x3f3f3f3f
#define MAX(a,b) ((a) >= (b) ? (a) : (b))

int n;
int D[Nmax];
int p[3][Nmax];
int q[2][Nmax];
int a[Nmax], b[Nmax], c[Nmax];

void citire()
{
	int i;

	scanf("%d\n", &n);
	for (i = 2; i <= n; ++i)
	{
		scanf("%d %d %d\n", &a[i], &b[i], &c[i]);
		if (a[i] > b[i]) swap(a[i], b[i]);
		if (a[i] > c[i]) swap(a[i], c[i]);
		if (b[i] > c[i]) swap(b[i], c[i]);
	}
}

void solve()
{
	int i, j, best = 0, ind1, ind2;

	D[0] = 0;

	D[1] = 1;
	p[1][1] = 1;
    	q[1][1] = 1;

	D[2] = 2;
	p[0][1] = 1;
	p[0][2] = 2;
	q[2][1] = 1;
	q[2][2] = 2;

	for (i = 3; i <= n; ++i)
	{
        memcpy(p[2], p[1], sizeof(p[1]));
		memcpy(p[1], p[0], sizeof(p[0]));

		D[i] = 0;

		if (b[i] == c[i])
		{
			c[i] = a[i];
			a[i] = b[i];
		}

		for (j = 1; j <= 2; ++j)
		{
			if (j == 1 && a[i] != b[i]) continue;

			if (D[i] < MAX(D[j - 1], D[i - j]) + 1)
			{
				D[i] = MAX(D[j - 1], D[i - j]) + 1;
				best = j;
			}
		}

		ind1 = ind2 = 0;

		for (j = 1; j <= i; ++j)
		{
 			if (j == b[i]) p[0][j] = best; 
			else if (j == a[i]) p[0][j] = q[best - 1][++ind1];
			else if (j == c[i]) p[0][j] = p[best][++ind2] + best;
			else if (best - 1 - ind1 >= i - best - ind2)
				p[0][j] = q[best - 1][++ind1];
			else if (best - 1 - ind1 < i - best - ind2)
				p[0][j] = p[best][++ind2] + best;
		}
	}

	printf("%d\n", D[n]);
	for (i = 1; i <= n; ++i)
		printf("%d ", p[0][i]);
	printf("\n");
}

int main()
{
	freopen("sortare.in", "r", stdin);
	freopen("sortare.out", "w", stdout);

	citire();
	solve();

	return 0;
}