Cod sursa(job #1791384)

Utilizator raulrusu99Raul Rusu raulrusu99 Data 29 octombrie 2016 12:09:59
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
#define MAX_N 100010
int n,m,vr[MAX_N],v[MAX_N],l[MAX_N],maxx,val;
vector <int> drum[MAX_N];
int caut_bin(int x)
{
    int in,sf,mij;
    in=1;
    sf=m;
    while(in<=sf)
    {
        mij=(in+sf)/2;
        if(vr[mij]<x) sf=mij-1;
        else in=mij+1;
    }
    return in;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i];
    for(int i=1;i<=n;i++)
    {
        int bin=caut_bin(v[i]);
        l[bin]++;
        drum[bin].push_back(v[i]);
        vr[bin]=v[i];
        if(bin>m) m++;
    }
    for(int i=1;i<=m;i++)
        if(maxx<l[i])
        {
            maxx=l[i];
            val=i;
        }
    g<<maxx<<"\n";
    for(int i=0;i<drum[val].size();i++)
        g<<drum[val][i]<<" ";
    return 0;
}