Pagini recente » Cod sursa (job #2869738) | Cod sursa (job #3192918) | Cod sursa (job #1218818) | Istoria paginii runda/concurs_info2018/clasament | Cod sursa (job #203727)
Cod sursa(job #203727)
using namespace std;
#include <cstdio>
#include <algorithm>
#define IN "subsir2.in"
#define OUT "subsir2.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define N_MAX 1<<13
int N;
int A[N_MAX],T[N_MAX],V[N_MAX];
char ch[(N_MAX)*5];
inline int better(int x,int y)
{
int l = A[x];
FOR(i,1,l)
{
if(V[x] < V[y])
return 1;
if(V[y] < V[x])
return 0;
x = T[x];
y = T[y];
}
return 0;
}
void scan()
{
int semn;
freopen(IN, "r",stdin);
freopen(OUT, "w",stdout);
scanf("%d\n", &N);
fgets(ch,1<<20,stdin);
V[0] = 1;
for(int i=0;ch[i] != '\0' && ch[i] !='\n';++i)
{
if(ch[i] == '-')
++i,semn = V[0];
V[ V[0] ] = V[ V[0] ] * 10 + ch[i] - '0';
if(ch[i+1] == ' ')
{
if(semn == V[0])
V[ V[0] ] *= -1;
++i,++V[0];
}
if(ch[i+1] == '-')
++i,semn = V[0];
}
}
void solve()
{
int best,minim;
A[0] = 1<<30;
V[0] = 1<<30;
bool ok;
for(int i=N;i>=1;--i)
{
best = ok = false;
minim = 0;
FOR(j,i+1,N)
if(V[j] >= V[i])
{
if( (A[j] < A[best] || (A[j] == A[best] && V[j] < V[best] ) ) && V[j] < V[minim])
{
best = j;
ok=1;
}
if(V[j] < V[minim])
minim = j;
}
if(ok)
A[i] = A[best] + 1,
T[i] = best;
else
A[i] = 1,
T[i] = i;
}
best = 0;
minim = 1<<30;
FOR(i,1,N)
{
if( (A[i] < A[best] || (A[i] == A[best] && better(i,best)) ) && V[i] < minim)
best = i;
minim = min(minim,V[i]);
}
printf("%d\n", A[best]);
int rez = best;
FOR(i,1,A[rez])
{
printf("%d ",best);
best = T[best];
}
}
int main()
{
scan();
solve();
return 0;
}