oj.uz

Submission #1117550

# Submission time Handle Problem Language Result Execution time Memory
1117550 2024-11-23T22:50:48 Z secretwood01 Global Warming (NOI13_gw) C++17
40 / 40
 390 ms 22188 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

class Element {
private:
  int nothing;
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
    }
};

bool funt(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;
}

int bs(std::vector<Element>& T) {
    int lo = 1;
    int hi = T.size();
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if (funt(mid, T)) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    return lo;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    std::vector<Element> Arr;
    for (int i = 0; i < N; i++) {
        int value;
        std::cin >> value;
        Arr.emplace_back(value, i);
    }
    std::sort(Arr.begin(), Arr.end());
    std::cout << bs(Arr) << std::endl;
    return 0;
}

Compilation message

gw.cpp: In function 'bool funt(int, std::vector<Element>&)':
gw.cpp:23:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Element>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     while (islands < mid && index < T.size()) {
      |                             ~~~~~~^~~~~~~~~~
gw.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Element>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         while (index < T.size() && T[index].val == currVal) {
      |                ~~~~~~^~~~~~~~~~
gw.cpp:29:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             bool right = curr.ind == v.size() - 1 || !v[curr.ind + 1];
      |                          ~~~~~~~~~^~~~~~~~~~~~~~~
gw.cpp:32:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             bool negRight = curr.ind != v.size() - 1 && v[curr.ind + 1];
      |                             ~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1992 KB Output is correct
2 Correct 17 ms 1992 KB Output is correct
3 Correct 22 ms 1992 KB Output is correct
4 Correct 16 ms 1992 KB Output is correct
5 Correct 17 ms 1992 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1992 KB Output is correct
2 Correct 14 ms 1992 KB Output is correct
3 Correct 24 ms 1992 KB Output is correct
4 Correct 25 ms 1992 KB Output is correct
5 Correct 26 ms 1992 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 14756 KB Output is correct
2 Correct 293 ms 22188 KB Output is correct
3 Correct 296 ms 22180 KB Output is correct
4 Correct 283 ms 22080 KB Output is correct
5 Correct 285 ms 21416 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 14780 KB Output is correct
2 Correct 390 ms 21480 KB Output is correct
3 Correct 310 ms 21416 KB Output is correct
4 Correct 186 ms 16460 KB Output is correct
5 Correct 179 ms 16572 KB Output is correct