Cod sursa(job #531466)

Utilizator ooctavTuchila Octavian ooctav Data 9 februarie 2011 18:42:11
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 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];
int bun[NMAX];//fac bitset
int sol[NMAX];

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

void init()
{
	fill(d + 1, d + NMAX, INF);
	fill(bun, bun + NMAX, 1);	
	fill(sol, sol + NMAX, INF);
}

void rezolva()
{
	d[0] = INF;
	IFOR(i, N, 1)
	{
		FOR(j, 1, i - 1)	if(a[j] <= a[i])	{bun[i] = 0; break;}
			
		int minim = INF, poz = 0;
		FOR(j, i + 1, N)
			if(a[i] <= a[j])
				if(minim == INF || a[j] < minim)
				{
					minim = a[j];
					if(d[j] < d[poz] || (d[j] == d[poz] && a[j] < a[poz]))	
						poz = j;
				}
		if(!poz)	d[i] = 1;
		else		{urm[i] = poz;d[i] = d[poz] + 1;}
	}
}

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()
{
	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();
	init();
	rezolva();
	alege_sol();
	scrie();
	return 0;
}