Cod sursa(job #413714)

Utilizator johnbBaranga Ionut johnb Data 8 martie 2010 23:53:07
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <fstream>
#include <stdlib.h>
#include <limits.h>

using namespace std;

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

struct item {
        int val;
        int idx;
};

int fcmp(const void* x,const void* y) {
    return ((item*)x)->val - ((item*)y)->val;

}

item* elem;

int main() {
    int n, x;
    in >> n;
    elem = new item[n];
    for (int i = 0; i < n; i++) {
        in >> x;
        elem[i].val = x;
        elem[i].idx = i;
    }
    item* elem2 = new item[n];
    for (int i = 0; i < n; i++)
        elem2[i] = elem[i];
    qsort(elem, n, sizeof(item), fcmp);
    item* aux = new item[n];
    for (int i = 0; i < n; i++) {
        aux[i].val = elem[i].idx;
        aux[i].idx = i;
    }
    qsort(aux, n, sizeof(item), fcmp);

    int max = 1, crtMax = 1, idx = 0, crtIdx = 0;
    for (int i = 1; i < n; i++) {
        if (aux[i - 1].idx < aux[i].idx) {      
              crtMax++;
        }
        else {
             if (crtMax > max) {
                        max = crtMax;
                        idx = crtIdx;          
             }
             crtMax = 1;
             crtIdx = i;
        }
    }
    if (crtMax > max) {
            max = crtMax ;
            idx = crtIdx;          
    }

    int crtVal = elem2[aux[idx].val].val, val;
    for (int i = 1; i < max ; i++) {
           val = elem2[aux[idx + i].val].val;
           if (val == crtVal) {
               max--;
           }
           crtVal = val;
    }
    
    out << max << "\n";
    crtVal = elem2[aux[idx].val].val, val;
    out << crtVal << " ";
    int j = 1;
    for (int i = 1; j < max ; i++) {
           val = elem2[aux[idx + i].val].val;
           if (val != crtVal) {
              out << val << " ";
              crtVal = val;
              j++;
           }
    }
    
    return 0;
}