Cod sursa(job #413705)

Utilizator johnbBaranga Ionut johnb Data 8 martie 2010 23:10:29
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 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) {
    int rez = ((item*)x)->val - ((item*)y)->val;
    if (rez != 0)
       return rez;
    return ((item*)x)->idx - ((item*)y)->idx;
}

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;
    }
    qsort(elem, n, sizeof(item), fcmp);

    int max = 1, crtMax = 1, idx = 0, crtIdx = 0;
    for (int i = 1; i < n; i++) {
        if (elem[i - 1].idx < elem[i].idx) {
           if (elem[i - 1].val != elem[i].val)        
              crtMax++;
        }
        else {
             if (crtMax > max) {
                        max = crtMax;
                        idx = crtIdx;          
             }
             crtMax = 1;
             crtIdx = i;
        }
    }
    if (crtMax > max) {
            max = crtMax;
            idx = crtIdx;          
    }
    out << max << "\n";
    out << elem[idx].val << " ";
    int j = 1;
    for (int i = 1; j < max ; i++)
         if (elem[idx + i].val != elem[idx + i - 1].val) {
           out << elem[idx + i].val << " ";
           j++;
         }
    
        
    
    return 0;
}