Pagini recente » Istoria paginii runda/simulare-cartita-13/clasament | Cod sursa (job #1733379) | Cod sursa (job #1165688) | Cod sursa (job #917381) | Cod sursa (job #315321)
Cod sursa(job #315321)
#include <cstdio>
#include <bitset>
#include <cstring>
using namespace std;
#define MAX_N 5005
#define INF 0x3f3f3f
int N, Nr = INF;
int V[MAX_N], S[MAX_N], Ant[MAX_N], Sol[MAX_N];
bitset <MAX_N> Tr;
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);
}
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;
if(max > S[j] && V[j] < min)
{
max = S[j];
Ant[i] = j;
}
min = Min(min, V[j]);
}
if(max) S[i] = S[Ant[i]] + 1;
}
for(int i = 1; i <= N; ++i)
{
int ok = 0;
for(int j = 1; j < i; ++j)
if(V[j] <= V[i])
ok = 1;
Tr[i] = ok;
}
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];
}
}
if(S[i] == Nr && Tr[i] == 0)
{
int k = i, p = 0, ok = 2;
while(k)
{
++p;
if(ok == 2)
if(V[k] < V[Sol[p]])
ok = 1;
else
ok = 0;
k = Ant[k];
}
if(ok)
{
int k = i, p = 0;
while(k)
{
Sol[++p] = k;
k = Ant[k];
}
}
}
}
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();
}