Pagini recente » Cod sursa (job #684898) | Cod sursa (job #3216982) | Cod sursa (job #11190) | Cod sursa (job #2376448) | Cod sursa (job #3265196)
#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;
}