Cod sursa(job #3265196)

Utilizator InformaticianInDevenire1Munteanu Mihnea Gabriel InformaticianInDevenire1 Data 27 decembrie 2024 21:52:33
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;

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

int v[100005],cv[100005];
map <int,int> Nrm;
int iNrm[100005];
int tata[100005];
vector <pair<int,int>> dp;
vector <int> ans;

int main()
{
    int n;
    fin >> n;
    dp.push_back({0,0});
    for (int i=1;i<=n;++i){
        fin >> v[i];
        cv[i] = v[i];
        dp.push_back({0,0});
    }
    sort(cv,cv+n+1);
    int Init = 0;
    for (int i=1;i<=n;++i){
        tata[i] = i;
        if (Nrm[cv[i]]>0) continue;
        Init++;
        Nrm[cv[i]] = Init;
        iNrm[Init] = cv[i];
    }
    int Size = 0;
    int Cmme = 0; // Cel mai mare element
    for (int i=1;i<=n;++i){
        pair loc = {0,0};
        int ind = 0;
        if (Nrm[v[i]]==1){
            dp[1] = {1,i};
            continue;
        }
        for (int j=1;j<=Nrm[v[i]]-1;++j){
            if (loc<dp[i]){
                loc = dp[i];
                ind = i;
            }
        }
        int frs = loc.first+1;
        dp[Nrm[v[i]]] = {frs,i};
        tata[Nrm[v[i]]] = loc.second;
        if (Size<frs){
            Size = frs;
            Cmme = Nrm[v[i]];
        }
    }
    int x = Cmme;
    ans.push_back(x);
    while (tata[x]!=x){
        x = tata[x];
        ans.push_back(x);
    }
    fout << Size << '\n';
    reverse(ans.begin(),ans.end());
    for (auto o:ans) fout << o << ' ';
    return 0;
}