Pagini recente » Cod sursa (job #1912258) | Cod sursa (job #1254319) | Cod sursa (job #2979324) | Cod sursa (job #1695606) | Cod sursa (job #2194613)
#include <cstdio>
using namespace std;
int n, v[5005], lengths[5005], positions[5005], seqCounter, lg, lt, rt, mid;
int main()
{
FILE *in, *out;
in = freopen("subsir2.in", "r", stdin);
out = freopen("subsir2.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
fclose(in);
for (int i = 1; i <= n; i++) {
if (v[i] > v[positions[seqCounter]]) {
positions[++seqCounter] = i;
lengths[i] = seqCounter;
}
else {
for (lt = 1, rt = seqCounter, lg = seqCounter; lt <= rt;) {
mid = lt + (rt - lt) / 2;
if (v[positions[mid]] < v[i]) lt = mid + 1;
else {
lg = mid;
rt = mid - 1;
}
}
positions[lg] = i;
lengths[i] = lg;
}
}
printf("%d\n", seqCounter);
for (int i = n, lg = 0; i && seqCounter; i--)
if (lengths[i] == seqCounter) {
positions[++lg] = i;
seqCounter--;
}
for (int i = lg; i; i--) printf("%d ", positions[i]);
fclose(out);
return 0;
}