foo.cpp

#include <algorithm>
#include <iostream>
#include <vector>

template <typename T>
bool foo(const std::vector<T>& v) {
    auto is_odd = [](auto&& i){ return i % 2 != 0; };
    if (!std::is_partitioned(begin(v), end(v), is_odd)) {
        return false;
    }

    auto p = std::partition_point(begin(v), end(v), is_odd);

    return std::is_sorted(begin(v), p);
}

int main() {
    const std::vector<int> good{1, 5, 9, 13, 21, 101, 1000, 2, 100, 30, 10};
    const std::vector<int> bad1{11, 5, 201, 2, 4, 0};
    const std::vector<int> bad2{1, 3, 5, 2, 9};

    std::cout << std::boolalpha;

    std::cout << foo(good) << std::endl;
    std::cout << foo(bad1) << std::endl;
    std::cout << foo(bad2) << std::endl;

    return 0;
}