Pagini recente » Borderou de evaluare (job #48538) | Cod sursa (job #2789943) | Cod sursa (job #522843)
Cod sursa(job #522843)
/*
* File: main.cpp
* Author: salexandru
*
* Created on January 15, 2011, 8:58 PM
*/
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 100011
using namespace std;
/*
*
*/
int f[N_MAX];
vector<int> TopMax, v;
inline void output( ostream& out, int& x, int size )
{
if( size )
{
output( out, f[x], size-1 );
out<<v[x]<<' ';
}
}
int main(int argc, char** argv)
{
int N, i, left, right, middle;
ifstream in( "scmax.in" );
in>>N;
copy( istream_iterator<int>(in), istream_iterator<int>(), back_inserter(v) );
TopMax.push_back(0);
for( i=1; i < N; ++i )
{
if( v[TopMax.back()] < v[i] )
{
f[i]=TopMax.back();
TopMax.push_back(i);
continue;
}
left=0; right=TopMax.size()-1;
while( left < right )
{
middle=(left+right)/2;
if( v[TopMax[middle]] == v[i] )
{
left=middle;
break;
}
if( v[TopMax[middle]] > v[i] )
right=middle;
else left=middle+1;
}
if( v[i] == v[TopMax[left]] )
continue;
if( v[i] <= v[TopMax[left]] )
{
if( left > 0 )
f[i]=TopMax[left-1];
TopMax[left]=i;
}
else TopMax.push_back(i);
}
ofstream out( "scmax.out" );
out<<TopMax.size()<<'\n';
output( out, TopMax.back(), TopMax.size() );
out<<'\n';
return 0;
}