Cod sursa(job #2672555)

Utilizator dvp123Pescariu David dvp123 Data 14 noiembrie 2020 10:46:40
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <vector>

#include <iostream>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n;
vector<int> found;

bool doesElementExistInVec(int elem, vector<int> vec) {
    /// Binary search because vec is ascending
    int mid = vec.size() / 2;
    int st = 0;
    int dr = vec.size();

    while(st < dr) {
        if (vec[mid] == elem) {
            return true;
        } else {
            if (vec[mid] < elem) {
                st = mid + 1;
            } else {
                dr = mid - 1;
            }
            mid = (st + dr) / 2;
        }
    }

    return false;
}

int main() {
    int last_number;
    int current_number;
    vector<int> longest_now;

    fin >> n;
    fin >> last_number;
    longest_now.push_back(last_number);

    for (int i=1; i<n; ++i) {
        fin >> current_number;
        if (current_number < last_number) {
            if (longest_now.size() > found.size()) {
                found = longest_now;
                longest_now.clear();
            }
            longest_now.push_back(current_number);
        } else if (!doesElementExistInVec(current_number, longest_now)) {
            longest_now.push_back(current_number);
        }
        last_number = current_number;
    }
    if (current_number < last_number) {
        if (longest_now.size() > found.size()) {
            found = longest_now;
        }
    }

    fout << longest_now.size() << "\n";
    for (int e : longest_now) {
        fout << e << " ";
    }
    fout << "\n";

    return 0;
}