Cod sursa(job #2676835)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 25 noiembrie 2020 09:05:21
Problema Subsir 2 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, v[5005], lung, p[5005], dp[5005];
struct idk{
    int d, i, val;
}aux[5005];

bool cmp(idk a, idk b){
    if (a.d == b.d){
        if (b.val == a.val)
            return a.i < b.i;
        return a.val < b.val;
    }
    return a.d > b.d;
}

int main(){
    fin >> n;
    for (int i = 1; i <= n; ++i){
        fin >> v[i];
    }
    for (int i = n; i >= 1; --i){
        int st = 1, dr = lung, pos = -1;
        while (st <= dr){
            int mid = (st + dr) / 2;
            if (v[i] > v[p[mid]]){
                pos = mid;
                dr = mid - 1;
            }
            else{
                st = mid + 1;
            }
        }
        if (pos == -1){
            p[++lung] = i;
            dp[i] = lung;
        }
        else{
            p[pos] = i;
            dp[i] = pos;
        }
        aux[i] = {dp[i], i, v[i]};
    }
    sort(aux + 1, aux + n + 1, cmp);
    fout << lung << "\n";
    int last1 = -1e9, last2 = -1;
    for (int i = 1; i <= n; ++i){
        if (aux[i].d == lung && aux[i].i > last2 && aux[i].val > last1){
            fout << aux[i].i << " ";
            last1 = aux[i].val;
            last2 = aux[i].i;
            --lung;
        }
    }
    fin.close();
    fout.close();
    return 0;
}