Cod sursa(job #289648)

Utilizator scvalexAlexandru Scvortov scvalex Data 26 martie 2009 21:19:56
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <cstdio>
#include <vector>

using namespace std;
typedef pair<int, int> pii;
vector< vector<pii> > p;
int r[100000];

void printp() {
	for (int i = 0; i < (int)p.size(); ++i) {
		printf("%2d: ", i);
		for (vector<pii>::iterator jj = p[i].begin(); jj != p[i].end(); ++jj)
			printf("%3d", jj->first);
		printf("\n");
	}
	printf("\n");

}

void printd() {
	for (int i = 0; i < (int)p.size(); ++i) {
		printf("%2d: ", i);
		for (vector<pii>::iterator jj = p[i].begin(); jj != p[i].end(); ++jj)
			printf("%3d", jj->second);
		printf("\n");
	}
	printf("\n");

}

int bisect_left(int l, int u, int k) {
	int i;
	for (i = 1; i < u-l+1; i <<= 1)
		;
	//printf("l: ");
	for (; i > 0; i >>= 1) {
		if ((l + i <= u) && (p[l+i].back().first <= k))
			l += i;
		//printf("%d ", l);
	}
	//printf("\n");
	
	if ((l <= u) && (k > p[l].back().first))
		++l;
	return l;
}

int main(int argc, char *argv[]) {
	FILE *fi = fopen("scmax.in", "r");
	int N;
	fscanf(fi, "%d", &N);
	p.push_back(vector<pii>());
	//printp();
	int pn = 1, a;
	while (N--) {
		fscanf(fi, "%d", &a);
		int pi = bisect_left(1, pn-1, a);
		//printf("%d\n", pi);
		if (pi == pn) {
			p.push_back(vector<pii>());
			++pn;
		}
		p[pi].push_back(make_pair(a, p[pi-1].size() - 1));
		//printp();
		//printd();
	}
	//printf("\n");
	fclose(fi);

	int prev = p[p.size()-1].size()-1;
	for (int i = p.size() - 1; i > 0; --i) {
		//printf("%d ", prev);
		r[i-1] = p[i][prev].first;
		prev = p[i][prev].second;
	}
	//printf("\n");

	FILE *fo = fopen("scmax.out", "w");
	fprintf(fo, "%d\n", (int)p.size()-1);
	for (int i = 0; i < (int)p.size()-1; ++i)
		fprintf(fo, "%d ", r[i]);
	fprintf(fo, "\n");
	fclose(fo);

	return 0;
}