Pagini recente » Cod sursa (job #404877) | Cod sursa (job #1091298) | Cod sursa (job #3122991) | Cod sursa (job #661834) | Cod sursa (job #1665865)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <bitset>
#include <stack>
#define MAX 100003
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");
struct st {
int p;
int s;
};
int v[MAX];
int o[MAX];
int b[MAX];
bitset<MAX> u;
vector<st> vct;
vector<vector<st>> stk;
vector<st> tmp;
vector<st> emp;
st temp;
int k;
int main() {
int n;
int maxF = 0;
in >> n;
for(int i = 0; i < n; i++) {
in >> v[i];
maxF = max(maxF, v[i]);
o[i] = 1;
b[i] = -1;
}
maxF++;
int mi;
int mx;
bool f = false;
for(int i = 1; i < n; i++) {
if(v[i-1] <= v[i]) {
o[i] = o[i-1]+1;
b[i] = i-1;
u[i-1] = 1;
}
mi = v[i-1];
mx = v[i-1];
f = false;
for(int j = i-2; j >= 0; j--) {
if(v[j] <= v[i] && v[i] < mi) {
if((o[j]+1 < o[i] || !f) || (o[j]+1 == o[i] && v[j]<v[b[i]])) {
o[i] = o[j]+1;
b[i] = j;
u[j] = 1;
f = true;
}
}
mi = min(v[j], mi);
}
}
int miP = -1;
for(int i = 0; i < n; i++) {
if(!u[i]) {
if(miP == -1) {
miP = i;
temp.p = temp.s = miP;
vct.push_back(temp);
} else {
if(o[i] < o[miP]) {
miP = i;
vct.resize(0);
temp.p = temp.s = i;
vct.push_back(temp);
} else if(o[i] == o[i]) {
temp.p = temp.s = i;
vct.push_back(temp);
}
}
}
}
int M = o[miP];
int P;
for(vector<st>::iterator it = vct.begin(); it != vct.end(); it++) {
P = it->p;
while(P != -1) {
temp.p = P;
temp.s = it->s;
tmp.push_back(temp);
P = b[P];
}
stk.push_back(tmp);
tmp = emp;
}
int PM = 0;
for(int i = M-1; i >= 0; i--) {
PM = v[stk.begin()->at(i).p];
for(vector<vector<st>>::iterator it = stk.begin(); it != stk.end(); it++)
PM = min(v[it->at(i).p], PM);
for(vector<vector<st>>::iterator it = stk.begin(); it != stk.end(); it++)
if(v[it->at(i).p] != PM)
stk.erase(it);
}
vector<vector<st>>::iterator stk2 = stk.begin();
out << M << '\n';
for(vector<st>::iterator it = stk2->end()-1; it != stk2->begin()-1; it--)
out << it->p+1 << " ";
return 0;
}