Pagini recente » Cod sursa (job #2723388) | Cod sursa (job #623286) | Cod sursa (job #2553904) | Cod sursa (job #3226458) | Cod sursa (job #2195296)
#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 = 1; i <= seqCounter; ++i) printf("%d ", positions[i]);
fclose(out);
return 0;
}