Pagini recente » Cod sursa (job #684763) | Cod sursa (job #1059326) | Cod sursa (job #178685) | Cod sursa (job #2250172) | Cod sursa (job #2676835)
#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;
}