Cod sursa(job #203699)

Utilizator rapidu36Victor Manz rapidu36 Data 18 august 2008 18:08:21
Problema Subsir 2 Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<stdio.h>

const int N=5001;

int v[N],v1[N],v2[N],n,x[N],nr;

void citire(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&v[i]);
}

int caut1(int y){
	int p=1,u=nr,m;
	m=(p+u)>>1;
	while(p!=u){
		m=(p+u)>>1;
		if(y<=x[m])
			u=m;
		else
			p=m+1;
	}
	if(x[p]<y)
		++p;
	return p;
}

int caut2(int y){
	int p=1,u=nr,m;
	m=(p+u)>>1;
	while(p!=u){
		m=(p+u)>>1;
		if(y>=x[m])
			u=m;
		else
			p=m+1;
	}
	if(x[p]>y)
		++p;
	return p;
}
/*
void proba(){
	for(int i=1;i<=nr;++i)
		printf("%d ",x[i]);
	printf("\n");
}

void probav1v2(){
	printf("\n");
	for(int i=1;i<=n;++i)
		printf("%d ",v1[i]);
	printf("\n");
	for(int i=1;i<=n;++i)
		printf("%d ",v2[i]);
	printf("\n");
}
*/
void calcul(){
	int poz;
	nr=0;
	x[++nr]=v[1];
	v1[1]=0;
	for(int i=2;i<=n;++i){
		poz=caut1(v[i]);
		if(poz>nr)
			++nr;
		v1[i]=poz-1;
		x[poz]=v[i];
	}
	//proba();
	nr=0;
	x[++nr]=v[n];
	v2[n]=0;
	for(int i=n-1;i>=1;--i){
		poz=caut2(v[i]);
		if(poz>nr)
			++nr;
		v2[i]=poz-1;
		x[poz]=v[i];
	}
	//proba();
	//probav1v2();
	poz=1;
	for(int i=2;i<=n;++i)
		if(v1[i]==0) 
			if(v2[i]<v2[poz] || (v2[i]==v2[poz] && v[i]<v[poz]))
				poz=i;
	int rest=v2[poz]+1,k,i;
	printf("%d\n%d",rest,poz);
	--rest;
	while(rest){
		k=rest--;
		for(i=poz+1;i<=n && v2[i]!=rest;++i)
			;
		poz=i;
		for(i=poz+1;i<=n;++i)
			if(v2[i]==rest && v[i]<v[poz])
				poz=i;
		printf(" %d",poz);
	}
	printf("\n");
}

int main(){
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	citire();
	calcul();
	return 0;
}