Cod sursa(job #531418)

Utilizator ooctavTuchila Octavian ooctav Data 9 februarie 2011 17:23:37
Problema Subsir 2 Scor 46
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;

const char IN[] = {"subsir2.in"};
const char OUT[] = {"subsir2.out"};
const int INF = 1000000005;
const double PI  = 3.14159265;
const int NMAX = 5005;
const int VALMAX = 1000005;

#define II inline
#define LL long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fs first
#define ss second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) 	for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b) 	for(int i = a ; i >= b ; i--)
#define FORIT(it, V) 	for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define zero(x) (x ^ (x - 1)) & x

int N;
int a[NMAX];
int d[NMAX], urm[NMAX], pre[NMAX];
int bun[NMAX];//fac bitset
int sol[NMAX];

void citi()
{
	scanf("%d", &N);
	FOR(i, 1, N)	scanf("%d", &a[i]);
}

void rezolva()
{
	fill(d + 1, d + N + 1, INF);
	a[0] = INF;
	FOR(i, 1, N)
	{
		if(d[i] == INF)	d[i] = 1, bun[i] = 1;
		int minim = INF, poz = 0;
		FOR(j, i + 1, N)
		{
			if(a[i] < a[j])
			{
				if(a[j] < minim)	minim = a[j], poz = j;
				if(d[i] < d[j] || (d[i] == d[j] && a[pre[i]] > a[j]))
				{
					d[j] = d[i] + 1;
					pre[j] = i;
				}
			}
			urm[i] = poz;
		}
	}
}

bool schimb(int x[], int y[])
{
	if(x[0] < y[0])			return 0;
	else if(x[0] > y[0])	return 1;
	FOR(i, 1, x[0])
		if(a[x[i]] < a[y[i]])			return 0;
		else if(a[x[i]] > a[y[i]])	return 1;
	return 0;
}

void alege_sol()
{
	fill(sol, sol + NMAX, INF);
	FOR(i, 1, N)
		if(bun[i])
		{
			int cr[NMAX] = {0};
			for(int j = i ; j <= N && j ; j = urm[j])
				cr[++cr[0]] = j;
			if(schimb(sol, cr))	copy(cr, cr + NMAX, sol);
		}
}

void scrie()
{
	printf("%d\n", sol[0]);
	FOR(i, 1, sol[0])	printf("%d ", sol[i]);
	printf("\n");
}

int main()
{
	freopen(IN, "r", stdin);
	freopen(OUT, "w", stdout);
	citi();
	rezolva();
	alege_sol();
	scrie();
	return 0;
}