| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1117540 | secretwood01 | Global Warming (NOI13_gw) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
class Element {
public:
int val;
int ind;
Element(int val, int ind) : val(val), ind(ind) {}
bool operator<(const Element& o) const {
return val > o.val; // For descending order
}
};
int bs(std::vector<Element>& T);
bool f(int mid, std::vector<Element>& T);
int gw() {
int N;
std::cin >> N;
std::vector<Element> Arr(N);
for (int i = 0; i < N; i++) {
int value;
std::cin >> value;
Arr[i] = Element(value, i);
}
std::sort(Arr.begin(), Arr.end());
std::cout << bs(Arr) << std::endl;
return 0;
}
int bs(std::vector<Element>& T) {
int lo = 1;
int hi = T.size();
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (f(mid, T)) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}
bool f(int mid, std::vector<Element>& T) {
int islands = 0;
int index = 0;
std::vector<bool> v(T.size(), false);
while (islands < mid && index < T.size()) {
int currVal = T[index].val;
while (index < T.size() && T[index].val == currVal) {
Element curr = T[index];
v[curr.ind] = true;
bool left = curr.ind == 0 || !v[curr.ind - 1];
bool right = curr.ind == v.size() - 1 || !v[curr.ind + 1];
if (left && right) islands++;
bool negLeft = curr.ind != 0 && v[curr.ind - 1];
bool negRight = curr.ind != v.size() - 1 && v[curr.ind + 1];
if (negLeft && negRight) islands--;
index++;
}
}
return islands >= mid;
}