Cod sursa(job #1674783)

Utilizator razvandRazvan Dumitru razvand Data 4 aprilie 2016 20:53:31
Problema Subsir 2 Scor 6
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <limits.h>
#include <bitset>

using namespace std;

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

int v[5003];
int t[5003];
int s[5003];
int o[5003];
int b[5003];
int aib[5003];
bitset<5003> T;
int k;
int n;

int query(int val) {
    int M = 0;
    for(int i = val; i > 0; i -= i&-i) {
        //cout << "TEST " << aib[i] << '\n';
        if(M == 0 || o[M] > o[aib[i]])
            M = aib[i];
    }
    return M;
}

int update(int val, int ind) {
    for(int i = val; i <= n; i += i&-i)
        if(o[ind] > o[aib[i]] || aib[i] == 0) {
            //cout << "SET " << '\n';
            aib[i] = ind;
        }
}

int main() {

    in >> n;

    for(int i = 1; i <= n; i++) {
        in >> v[i];
        s[i] = v[i];
        t[i] = v[i];
    }

    sort(s+1, s+n+1);

    for(int i = 1; i <= n; i++)
        v[i] = lower_bound(s, s+n, v[i])-s;

    int M = INT_MAX;
    int MI = 0;

    for(int i = n; i >= 1; i--) {
        int q = query(n+1-(v[i]+1));
        o[i] = o[q]+1;
        b[i] = q;
        update(n+1-v[i], i);
    }

    int MIT = INT_MAX;

    for(int i = 1; i <= n; i++) {
        if(t[i] > MIT)
            T[i] = 1;
        else
            MIT = t[i];
        if(!T[i]) {
            if(o[i] < M) {
                M = o[i];
                MI = i;
            } else if(o[i] == M && t[i] < t[MI]) {
                M = o[i];
                MI = i;
            }
        }
        //cout << o[i] << " ";
    }

    out << M << '\n';
    while(MI != 0) {
        out << MI << " ";
        MI = b[MI];
    }

    return 0;
}