Cod sursa(job #1674790)

Utilizator razvandRazvan Dumitru razvand Data 4 aprilie 2016 20:58:15
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#define MAX 100003
#define MAXV 1000003

using namespace std;

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

int v[MAX];
int o[MAX];
int b[MAX];
bitset<MAX> u;
int k;

int main() {

    int n;
    in >> n;

    for(int i = 0; i < n; i++) {
        in >> v[i];
        o[i] = 1;
        b[i] = -1;
    }

    int mi;
    bool f = false;

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

        mi = MAXV;
        o[i] = MAX;

        for(int j = i+1; j < n; j++) {

            if(v[j] >= v[i] && v[j] < mi) {

                if(o[j]+1 < o[i] || (o[j]+1 == o[i] && v[j]<v[b[i]])) {

                    o[i] = o[j]+1;
                    b[i] = j;

                }

            }

            if(v[i] <= v[j])
                u[j] = 1;

            if(v[j] >= v[i])
                mi = min(mi, v[j]);

        }

        if(o[i] == MAX)
            o[i] = 1;

    }

    int MI = MAX;
    int miP = 0;

    for(int i = 0; i < n; i++) {
        if(!u[i]) {

            if(o[i] < MI || (o[i] == MI && v[i]<v[miP])) {

                MI = o[i];
                miP = i;

            }

        }
    }

    out << MI << '\n';

    while(miP != -1) {

        out << miP+1 << " ";
        miP = b[miP];

    }

    return 0;
}