Mai intai trebuie sa te autentifici.
Cod sursa(job #1610897)
Utilizator | Data | 23 februarie 2016 20:04:07 | |
---|---|---|---|
Problema | Subsir 2 | Scor | 45 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.34 kb |
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");
int v[100003];
int s[100003];
int o[100003];
int k;
int main() {
int n;
in >> n;
for(int i = 0; i < n; i++) {
in >> v[i];
s[i] = -1000003;
}
for(int i = 0; i < n; i++) {
if(v[i] > s[k-1]) {
s[k++] = v[i];
o[i] = k-1;
continue;
}
if(v[i] < s[0]) {
s[0] = v[i];
o[i] = 0;
continue;
}
int poz = upper_bound(s, s+k, v[i])-s;
if(s[poz-1] != v[i]) {
s[poz] = v[i];
o[i] = poz;
}
}
int ct = k-1;
out << k << '\n';
stack<int> st;
int mi = 1000000;
int pz = 0;
for(int i = n-1; i >= 0; i--) {
if(ct == o[i]) {
if(v[i] < mi) {
mi = v[i];
pz = i;
}
if(i == 0 || o[i] != o[i-1]) {
st.push(pz+1);
mi = 1000000;
ct--;
}
if(ct == -1)
break;
}
}
while(!st.empty()) {
out << st.top() << " ";
st.pop();
}
return 0;
}