Cod sursa(job #1713226)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 4 iunie 2016 22:47:24
Problema Subsir 2 Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <algorithm>
#define MAX 2000000
using namespace std;
  
char f[MAX];
int pos=0,size[100005]={},bef[100005]={},N,v[100005]={},used[100005]={},L;
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);
	r(N);
    for(int i=1;i<=N;i++)
        r(v[i]);
    for(int i=N;i>0;i--)
    {
        size[i]=1,bef[i]=0;
        for(int j=i+1;j<=N;j++)
        {
			if(v[i]<v[j]&&size[i]<1+size[j]||(size[i]==1+size[j]&&v[bef[i]]>v[j]))
            {
                size[i]=1+size[j];
				if(v[bef[i]]>v[j]||bef[i]==0)bef[i]=j;
            }
			if(v[i]<v[j])
				used[j]=true;
		}
	}
	int Min=N,pos=N;
    for(int i=N;i>0;i--)
		if(!used[i])
			if(size[i]<Min||(size[i]==Min&&v[i]<v[pos]))
				Min=size[i],pos=i;
	printf("%d\n%d ",Min,pos);
	while(bef[pos]>0)
	{
		printf("%d ",bef[pos]);
		pos=bef[pos];
	}
    return 0;
}