Submission #1117541

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1117541	2024-11-23T22:20:54 Z	secretwood01	Global Warming (NOI13_gw)	C++17	Compilation error	0 ms	0 KB

#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 main() {
    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;
}

Compilation message

gw.cpp: In function 'bool f(int, std::vector<Element>&)':
gw.cpp:51:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Element>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while (islands < mid && index < T.size()) {
      |                             ~~~~~~^~~~~~~~~~
gw.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Element>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while (index < T.size() && T[index].val == currVal) {
      |                ~~~~~~^~~~~~~~~~
gw.cpp:57:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             bool right = curr.ind == v.size() - 1 || !v[curr.ind + 1];
      |                          ~~~~~~~~~^~~~~~~~~~~~~~~
gw.cpp:60:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             bool negRight = curr.ind != v.size() - 1 && v[curr.ind + 1];
      |                             ~~~~~~~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/alloc_traits.h:33,
                 from /usr/include/c++/10/ext/alloc_traits.h:34,
                 from /usr/include/c++/10/bits/basic_string.h:40,
                 from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from gw.cpp:1:
/usr/include/c++/10/bits/stl_construct.h: In instantiation of 'void std::_Construct(_Tp*, _Args&& ...) [with _Tp = Element; _Args = {}]':
/usr/include/c++/10/bits/stl_uninitialized.h:567:18:   required from 'static _ForwardIterator std::__uninitialized_default_n_1<_TrivialValueType>::__uninit_default_n(_ForwardIterator, _Size) [with _ForwardIterator = Element*; _Size = long unsigned int; bool _TrivialValueType = false]'
/usr/include/c++/10/bits/stl_uninitialized.h:623:20:   required from '_ForwardIterator std::__uninitialized_default_n(_ForwardIterator, _Size) [with _ForwardIterator = Element*; _Size = long unsigned int]'
/usr/include/c++/10/bits/stl_uninitialized.h:685:44:   required from '_ForwardIterator std::__uninitialized_default_n_a(_ForwardIterator, _Size, std::allocator<_Tp>&) [with _ForwardIterator = Element*; _Size = long unsigned int; _Tp = Element]'
/usr/include/c++/10/bits/stl_vector.h:1606:36:   required from 'void std::vector<_Tp, _Alloc>::_M_default_initialize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = Element; _Alloc = std::allocator<Element>; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
/usr/include/c++/10/bits/stl_vector.h:512:9:   required from 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const allocator_type&) [with _Tp = Element; _Alloc = std::allocator<Element>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<Element>]'
gw.cpp:22:31:   required from here
/usr/include/c++/10/bits/stl_construct.h:109:7: error: no matching function for call to 'Element::Element()'
  109 |     { ::new(static_cast<void*>(__p)) _Tp(std::forward<_Args>(__args)...); }
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
gw.cpp:10:5: note: candidate: 'Element::Element(int, int)'
   10 |     Element(int val, int ind) : val(val), ind(ind) {}
      |     ^~~~~~~
gw.cpp:10:5: note:   candidate expects 2 arguments, 0 provided
gw.cpp:6:7: note: candidate: 'constexpr Element::Element(const Element&)'
    6 | class Element {
      |       ^~~~~~~
gw.cpp:6:7: note:   candidate expects 1 argument, 0 provided
gw.cpp:6:7: note: candidate: 'constexpr Element::Element(Element&&)'
gw.cpp:6:7: note:   candidate expects 1 argument, 0 provided