Mai intai trebuie sa te autentifici.

Cod sursa(job #1610897)

Utilizator razvandRazvan Dumitru razvand Data 23 februarie 2016 20:04:07
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>

using namespace std;

ifstream in("subsir2.in");
ofstream out("subsir2.out");

int v[100003];
int s[100003];
int o[100003];
int k;

int main() {

    int n;
    in >> n;

    for(int i = 0; i < n; i++) {
        in >> v[i];
        s[i] = -1000003;
    }

    for(int i = 0; i < n; i++) {
        if(v[i] > s[k-1]) {
            s[k++] = v[i];
            o[i] = k-1;
            continue;
        }
        if(v[i] < s[0]) {
            s[0] = v[i];
            o[i] = 0;
            continue;
        }
        int poz = upper_bound(s, s+k, v[i])-s;
        if(s[poz-1] != v[i]) {
            s[poz] = v[i];
            o[i] = poz;
        }
    }
    int ct = k-1;
    out << k << '\n';

    stack<int> st;
    int mi = 1000000;
    int pz = 0;

    for(int i = n-1; i >= 0; i--) {

        if(ct == o[i]) {

            if(v[i] < mi) {
                mi = v[i];
                pz = i;
            }

            if(i == 0 || o[i] != o[i-1]) {

                st.push(pz+1);
                mi = 1000000;
                ct--;

            }

            if(ct == -1)
                break;

        }

    }

    while(!st.empty()) {

        out << st.top() << " ";
        st.pop();

    }

    return 0;
}