Pagini recente » Cod sursa (job #2109104) | Cod sursa (job #2662189) | Cod sursa (job #2238624) | Borderou de evaluare (job #2051276) | Cod sursa (job #876390)
Cod sursa(job #876390)
#include<cstdio>
#define MAX_N 50005
FILE *f=fopen("subsir2.in","r");
FILE *g=fopen("subsir2.out","w");
using namespace std;
int n,v[MAX_N],len[MAX_N],next[MAX_N],poz[MAX_N];
bool check[MAX_N];
inline void read ( void )
{
fscanf(f,"%d",&n);
for( int index(1) ; index <= n; ++index)
fscanf(f,"%d", &v[index]);
}
inline void write ( void )
{
int minimum=1<<30;
int start_position;
for( int i= 1; i <= n; ++i)
if(check[i]==true)
{
if(len[i]<minimum)
{
minimum=len[i];
start_position=i;
}
else
if(len[i]==minimum && v[start_position]>v[i])
start_position=i;
}
fprintf(g,"%d\n%d ",len[start_position],start_position);
while(next[start_position]!=start_position)
{
fprintf(g,"%d ",next[start_position]);
start_position=next[start_position];
}
}
inline void solve ( void )
{
int i;
for( i=n; i>=1 ; --i)
{
len[i]=1;
next[i]=i;
check[i]=true;
int minim=1<<30;
int min=1000001;
for(int j = i+1 ; j <= n ; ++j )
{
if( v[j] > v[i])
{
if( len[j]<minim && v[j]<min )
{
minim=len[j];
next[i]=j;
len[i]=len[j]+1;
}
else
if( len[j]==minim && v[j]<min && v[j] <= v[next[i]])
next[i]=j;
if(v[j]<min)
min=v[j];
check[j]=false;
}
}
}
write();
}
int main()
{
read();
solve();
return 0;
}