Pagini recente » Cod sursa (job #2035440) | Cod sursa (job #2887018) | Cod sursa (job #2800216) | Cod sursa (job #2685934) | Cod sursa (job #1674790)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#define MAX 100003
#define MAXV 1000003
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");
int v[MAX];
int o[MAX];
int b[MAX];
bitset<MAX> u;
int k;
int main() {
int n;
in >> n;
for(int i = 0; i < n; i++) {
in >> v[i];
o[i] = 1;
b[i] = -1;
}
int mi;
bool f = false;
for(int i = n-2; i >= 0; i--) {
mi = MAXV;
o[i] = MAX;
for(int j = i+1; j < n; j++) {
if(v[j] >= v[i] && v[j] < mi) {
if(o[j]+1 < o[i] || (o[j]+1 == o[i] && v[j]<v[b[i]])) {
o[i] = o[j]+1;
b[i] = j;
}
}
if(v[i] <= v[j])
u[j] = 1;
if(v[j] >= v[i])
mi = min(mi, v[j]);
}
if(o[i] == MAX)
o[i] = 1;
}
int MI = MAX;
int miP = 0;
for(int i = 0; i < n; i++) {
if(!u[i]) {
if(o[i] < MI || (o[i] == MI && v[i]<v[miP])) {
MI = o[i];
miP = i;
}
}
}
out << MI << '\n';
while(miP != -1) {
out << miP+1 << " ";
miP = b[miP];
}
return 0;
}