Cod sursa(job #2194611)

Utilizator dragos.galeteanu2001Dragos Iulian dragos.galeteanu2001 Data 13 aprilie 2018 21:18:22
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include "stdafx.h"
#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;
}