Cod sursa(job #824045)

Utilizator mi5humihai draghici mi5hu Data 25 noiembrie 2012 20:19:02
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <stdio.h>
#define maxN 100100

int v[maxN];      // preturi
int lastEL[maxN]; // pretul ultimului produs din subsirul cu lung "i"
int pozV[maxN];   // pozitia in "v" a ultimului produs din subsirul cu lung "i"
int prev[maxN];   // prev[i] = pretul cadoului cumparat inaintea cadoului cu pretul "i"
int n;
int lastEL_AvailableP = 2;

int bsearch(int val, int st, int dr) {
	int mid = (st + dr) / 2;
		
	if (st == dr) {
		if (lastEL[mid] < val) {
			return mid + 1;
		} else {
			return -1;
		}
	}
			
	if (lastEL[mid + 1] <= val) {
		return bsearch(val, mid + 1, dr); 
	}
	if (lastEL[mid] > val) {
		if (mid != 1)return bsearch(val, st, mid);
	} 
	return mid + 1;	
}

void print(int poz) {
	if (poz == -1) {
		return;
	} else {
		print(prev[poz]);
		printf("%d ", v[poz]);
	}
}


int main(int argc, char** argv) {
	int poz;

	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	
	scanf("%d", &n);
	
	scanf("%d", &v[0]);
	lastEL[1] = v[0];
	pozV[1] = 0;
	prev[0] = -1;
	
	for (int i = 1; i < n; i++) {
		scanf("%d", &v[i]);
		
		//caut cel mai lung subsir ce are ultima valoare < v[i]
		poz = bsearch(v[i], 1, lastEL_AvailableP - 1);
		if (poz == -1) {
		} else if (poz >= lastEL_AvailableP) {
			lastEL[lastEL_AvailableP] = v[i];
			pozV[lastEL_AvailableP] = i;
			prev[i] = pozV[lastEL_AvailableP - 1];
			lastEL_AvailableP++;
		} else {
			lastEL[poz] = v[i];
			pozV[poz] = i;
			if (poz > 0) {
				prev[i] = pozV[poz - 1];
			} else {
				prev[i] = -1;
			}
		}	
	} 
	
	poz = lastEL_AvailableP - 1;
	printf("%d\n", lastEL_AvailableP - 1);
	print(pozV[poz]);
	
	return 0;
}