Pagini recente » Istoria paginii runda/simumaster/clasament | Cod sursa (job #2640496) | Istoria paginii runda/preoji2010 | Cod sursa (job #1977432) | Cod sursa (job #315308)
Cod sursa(job #315308)
#include <cstdio>
#include <cstring>
#define MAX_N 5005
#define INF 1000005
int N, Nr = INF;
int V[MAX_N], S[MAX_N], Ant[MAX_N], Sol[MAX_N], Tr[MAX_N];
void citire()
{
scanf("%d",&N);
for(int i = 1; i <= N; ++i)
scanf("%d",V+i);
}
inline int Min(const int &A, const int &B)
{
return ((A) < (B))? (A) : (B);
}
inline bool cmp(int A[MAX_N], int B[MAX_N], int Nr)
{
for(int i = 1; i <= Nr; ++i)
{
if(A[i] < B[i]) return 1;
if(A[i] > B[i]) return 0;
}
return 0;
}
void solve()
{
for(int i = N; i; --i)
{
Ant[i] = 0;
S[i] = 1;
int max = INF, min = INF;
for(int j = i+1; j <= N; ++j)
if(V[i] <= V[j])
{
if(max == S[j] && V[j] < min)
{
Ant[i] = j,
Tr[j] = 1;
}
if(max > S[j] && V[j] < min)
{
max = S[j];
Ant[i] = j;
Tr[j] = 1;
}
min = Min(min, V[j]);
}
if(max) S[i] = S[Ant[i]] + 1;
}
#ifdef _HOME_
for(int i = 1; i <= N; ++i)
fprintf(stderr,"%d %d %d %d\n",V[i], S[i], Ant[i], Tr[i]);
#endif
for(int i = 1; i <= N; ++i)
{
if(S[i] < Nr && Tr[i] == 0)
{
Nr = S[i];
int k = i, p = 0;
while(k)
{
Sol[++p] = k;
k = Ant[k];
}
#ifdef _HOME_
for(int i = 1; i <= Nr; ++i)
fprintf(stderr,"%d ",Sol[i]);
fprintf(stderr,"\n");
#endif
}
if(S[i] == Nr && Tr[i] == 0)
{
int Aux[MAX_N];
int k = i, p = 0, ok = 2;
while(k)
{
Aux[++p] = k;
k = Ant[k];
if(ok == 2)
if(V[Aux[p]] < V[Sol[p]])
ok = 1;
else
ok = 0;
}
if(ok)
{
memcpy(Sol, Aux, sizeof Aux);
#ifdef _HOME_
for(int i = 1; i <= Nr; ++i)
fprintf(stderr,"%d ",Sol[i]);
fprintf(stderr,"\n");
#endif
}
}
}
printf("%d\n",Nr);
for(int i = 1; i <= Nr; ++i)
printf("%d ",Sol[i]);
}
int main()
{
freopen("subsir2.in","rt",stdin);
freopen("subsir2.out","wt",stdout);
citire();
solve();
}