Pagini recente » Cod sursa (job #3243251) | Cod sursa (job #2270317) | Cod sursa (job #158598) | Cod sursa (job #1467257) | Cod sursa (job #3227593)
//nlogn
#include <bits/stdc++.h>
#define maxN 10005
using namespace std;
int n, i, j, v[maxN], sol[maxN], lu[maxN], pozitii[maxN];
int st, dr, mij, poz, k;
int main()
{
ifstream f("scmax.in");
ofstream g("scmax.out");
f >> n;
for(i = 1; i <= n; i ++)
f >> v[i];
for(i = 1; i <= n; i ++)
{
if(v[i] > sol[k]) sol[++ k] = v[i], pozitii[k] = i, lu[i] = k;
else
{
st = 1, dr = k, poz = k;
while(st <= dr)
{
mij = (st + dr) / 2;
if(sol[mij] < v[i]) st = mij + 1;
else dr = mij - 1, poz = mij;
}
sol[poz] = v[i], pozitii[poz] = i;
lu[i] = poz;
}
}
g << k << '\n';
for(i = n, j = 0; i > 0 && k; i --)
if(lu[i] == k) sol[++ j] = v[i], pozitii[j] = i, k --;
for(i = j; i >= 1; i --)
g << pozitii[i] << " ";
return 0;
}