Pagini recente » Borderou de evaluare (job #1179141) | Cod sursa (job #1382416)
#include <stdio.h>
#define NMAX 100000
int v[NMAX], m[NMAX], p[NMAX];
void out(FILE *fout, int pos)
{
if (pos > 0) {
out(fout, p[pos]);
fprintf(fout, "%d ", v[pos]);
}
}
int main()
{
FILE *fin, *fout;
fin = fopen("scmax.in", "r");
fout = fopen("scmax.out", "w");
int N;
fscanf(fin, "%d", &N);
int i;
for (i = 0; i < N; ++i) {
fscanf(fin, "%d", v + i);
}
int ss = 0;
for (i = 0; i < N; ++i) {
int l = 1, r = ss + 1;
while (l < r) {
int med = (l + r) / 2;
if (v[m[med]] < v[i]) {
l = med + 1;
} else {
r = med;
}
}
p[i] = m[l - 1];
m[l] = i;
if (l > ss) {
ss = l;
}
}
fprintf(fout, "%d\n", ss);
out(fout, m[ss]);
fclose(fin);
fclose(fout);
return 0;
}