Pagini recente » Cod sursa (job #3192436) | Cod sursa (job #1999960) | Cod sursa (job #44328) | Cod sursa (job #2044127) | Cod sursa (job #203699)
Cod sursa(job #203699)
#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;
}