Cod sursa(job #1713271)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 5 iunie 2016 01:07:00
Problema Subsir 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <algorithm>
#define MAX 2000000
#define INF 200000005
using namespace std;
  
char f[MAX];
int Pos=0,size[100005]={},bef[100005]={},N,v[100005]={},used[100005]={},L,M,P,start;
void r(int &nr)
{
    nr=0;
    while(f[Pos]<'0'||f[Pos]>'9')
        Pos++;
    while(f[Pos]>='0'&&f[Pos]<='9')
        nr=nr*10+f[Pos++]-'0';
}
 
int main()
{
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
  
    //fread(f,1,MAX,stdin);
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d",&v[i]);
    for(int i=N;i>0;i--)
    {
        size[i]=INF,bef[i]=P=0,M=INF;
        for(int j=i+1;j<=N;j++)
        {
			if(v[i]<v[j])
			{
				if(P==0||v[P]>v[j])P=j;
				if(v[j]<M&&size[i]>size[j]+1||(size[i]==size[j]+1&&v[P]<v[bef[i]]))size[i]=size[j]+1,bef[i]=j;
				if(v[j]<M)M=v[j];
			}	
		}
		if(size[i]==INF)size[i]=1,bef[i]=0;
	}
	M=INF,start=1;
	for(int i=1;i<=N;i++)
		if(M>v[i])
		{
			M=v[i];
			if(size[i]<size[start]||(size[i]==size[start]&&v[i]<v[start]))
				start=i;
		}
	printf("%d\n%d ",size[start],start);
	while(bef[start]>0)
	{
		printf("%d ",bef[start]);
		start=bef[start];
	}
    return 0;
}