Pagini recente » Cod sursa (job #1166414) | Cod sursa (job #1893306) | Cod sursa (job #1747012) | Cod sursa (job #2141425) | Cod sursa (job #1674783)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <limits.h>
#include <bitset>
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");
int v[5003];
int t[5003];
int s[5003];
int o[5003];
int b[5003];
int aib[5003];
bitset<5003> T;
int k;
int n;
int query(int val) {
int M = 0;
for(int i = val; i > 0; i -= i&-i) {
//cout << "TEST " << aib[i] << '\n';
if(M == 0 || o[M] > o[aib[i]])
M = aib[i];
}
return M;
}
int update(int val, int ind) {
for(int i = val; i <= n; i += i&-i)
if(o[ind] > o[aib[i]] || aib[i] == 0) {
//cout << "SET " << '\n';
aib[i] = ind;
}
}
int main() {
in >> n;
for(int i = 1; i <= n; i++) {
in >> v[i];
s[i] = v[i];
t[i] = v[i];
}
sort(s+1, s+n+1);
for(int i = 1; i <= n; i++)
v[i] = lower_bound(s, s+n, v[i])-s;
int M = INT_MAX;
int MI = 0;
for(int i = n; i >= 1; i--) {
int q = query(n+1-(v[i]+1));
o[i] = o[q]+1;
b[i] = q;
update(n+1-v[i], i);
}
int MIT = INT_MAX;
for(int i = 1; i <= n; i++) {
if(t[i] > MIT)
T[i] = 1;
else
MIT = t[i];
if(!T[i]) {
if(o[i] < M) {
M = o[i];
MI = i;
} else if(o[i] == M && t[i] < t[MI]) {
M = o[i];
MI = i;
}
}
//cout << o[i] << " ";
}
out << M << '\n';
while(MI != 0) {
out << MI << " ";
MI = b[MI];
}
return 0;
}