Cod sursa(job #1665865)

Utilizator razvandRazvan Dumitru razvand Data 27 martie 2016 13:55:06
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <bitset>
#include <stack>
#define MAX 100003

using namespace std;

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

struct st {
    int p;
    int s;
};

int v[MAX];
int o[MAX];
int b[MAX];
bitset<MAX> u;
vector<st> vct;
vector<vector<st>> stk;
vector<st> tmp;
vector<st> emp;
st temp;
int k;

int main() {

    int n;
    int maxF = 0;
    in >> n;

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

    int mi;
    int mx;
    bool f = false;

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

        if(v[i-1] <= v[i]) {
            o[i] = o[i-1]+1;
            b[i] = i-1;
            u[i-1] = 1;
        }

        mi = v[i-1];
        mx = v[i-1];
        f = false;

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

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

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

                    o[i] = o[j]+1;
                    b[i] = j;
                    u[j] = 1;
                    f = true;

                }

            }

            mi = min(v[j], mi);

        }

    }

    int miP = -1;

    for(int i = 0; i < n; i++) {
        if(!u[i]) {
            if(miP == -1) {
                miP = i;
                temp.p = temp.s = miP;
                vct.push_back(temp);
            } else {
                if(o[i] < o[miP]) {
                    miP = i;
                    vct.resize(0);
                    temp.p = temp.s = i;
                    vct.push_back(temp);
                } else if(o[i] == o[i]) {
                    temp.p = temp.s = i;
                    vct.push_back(temp);
                }
            }
        }
    }

    int M = o[miP];
    int P;

    for(vector<st>::iterator it = vct.begin(); it != vct.end(); it++) {

        P = it->p;
        while(P != -1) {
            temp.p = P;
            temp.s = it->s;
            tmp.push_back(temp);
            P = b[P];
        }

        stk.push_back(tmp);
        tmp = emp;

    }

    int PM = 0;

    for(int i = M-1; i >= 0; i--) {
        PM = v[stk.begin()->at(i).p];
        for(vector<vector<st>>::iterator it = stk.begin(); it != stk.end(); it++)
            PM = min(v[it->at(i).p], PM);
        for(vector<vector<st>>::iterator it = stk.begin(); it != stk.end(); it++)
            if(v[it->at(i).p] != PM)
                stk.erase(it);
    }

    vector<vector<st>>::iterator stk2 = stk.begin();

    out << M << '\n';

    for(vector<st>::iterator it = stk2->end()-1; it != stk2->begin()-1; it--)
        out << it->p+1 << " ";

    return 0;
}