Submission #346510

#	Time	Username	Problem	Language	Result	Execution time	Memory
346510		wleung_bvg	Triangles (CEOI18_tri)	C++17	Compilation error	0 ms	0 KiB

tri

#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int sz(const C&c){return int(c.size());}
using ll=long long;constexpr const char nl='\n',sp=' ';

namespace local_checker {
  vector<pair<ll, ll>> P;
  int query_count = 0;

  int get_n() {
    mt19937 rng(time(0));
    int N = 40000;
    for (int i = 0; i < N; i++) P.emplace_back(rng() % ll(1e9), rng() % ll(1e9));
    return N;
  }

  bool _clockwise_points(const pair<ll, ll> &a, const pair<ll, ll> &b, const pair<ll, ll> &c) {
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first) < 0;
  }

  bool is_clockwise(int a, int b, int c) {
    assert(query_count++ < 1e6);
    return _clockwise_points(P[a - 1], P[b - 1], P[c - 1]);
  }

  void give_answer(int s) {
    vector<pair<ll, ll>> hull;
    sort(P.begin(), P.end());
    for (int phase = 0; phase < 2; phase++) {
      for (int i = 0, st = sz(hull); i < sz(P); i++) {
        while (sz(hull) >= st + 2 && _clockwise_points(hull[sz(hull) - 2], hull[sz(hull) - 1], P[i])) hull.pop_back();
        hull.push_back(P[i]);
      }
      hull.pop_back(); reverse(P.begin(), P.end());
    }
    if (sz(hull) == 2 && hull[0] == hull[1]) hull.pop_back();
    if (hull.empty() && !P.empty()) hull.push_back(P[0]);
    cout << sz(hull) << sp << s << endl;
    assert(sz(hull) == s);
  }
}

// using namespace local_checker;

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // freopen("err.txt", "w", stderr);
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int N = get_n();
  int one = 1, two = 2;
  vector<vector<int>> side(2, vector<int>{two});
  for (int i = 1; i <= N; i++) if (i != one && i != two) side[is_clockwise(one, two, i)].push_back(i);
  for (int h = 0; h < 2; h++) {
    sort(side[h].begin(), side[h].end(), [&] (int i, int j) {
      return is_clockwise(one, i, j);
    });
    vector<int> temp;
    for (int i : side[h]) {
      while (sz(temp) >= 2 && !is_clockwise(temp[sz(temp) - 2], temp.back(), i)) temp.pop_back();
      temp.push_back(i);
    }
    side[h] = temp;
  }
  reverse(side[1].begin(), side[1].end());
  side[0].insert(side[0].begin(), one);
  side[0].pop_back();
  for (int h = 0; h < 2; h++) {
    bool done = false;
    while (!done) {
      done = true;
      for (int i = 0; i < 2; i++) {
        if (sz(side[h ^ i]) >= 2 && is_clockwise(side[h ^ i][sz(side[h ^ i]) - 2], side[h ^ i].back(), side[!(h ^ i)].back()) == i) {
          side[h ^ i].pop_back();
          done = false;
        }
      }
    }
    for (int i = 0; i < 2; i++) reverse(side[i].begin(), side[i].end());
  }
  give_answer(sz(side[0]) + sz(side[1]));
  return 0;
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:50:11: error: 'get_n' was not declared in this scope; did you mean 'local_checker::get_n'?
   50 |   int N = get_n();
      |           ^~~~~
      |           local_checker::get_n
tri.cpp:10:7: note: 'local_checker::get_n' declared here
   10 |   int get_n() {
      |       ^~~~~
tri.cpp:53:63: error: 'is_clockwise' was not declared in this scope; did you mean 'local_checker::is_clockwise'?
   53 |   for (int i = 1; i <= N; i++) if (i != one && i != two) side[is_clockwise(one, two, i)].push_back(i);
      |                                                               ^~~~~~~~~~~~
      |                                                               local_checker::is_clockwise
tri.cpp:21:8: note: 'local_checker::is_clockwise' declared here
   21 |   bool is_clockwise(int a, int b, int c) {
      |        ^~~~~~~~~~~~
tri.cpp: In lambda function:
tri.cpp:56:14: error: 'is_clockwise' was not declared in this scope; did you mean 'local_checker::is_clockwise'?
   56 |       return is_clockwise(one, i, j);
      |              ^~~~~~~~~~~~
      |              local_checker::is_clockwise
tri.cpp:21:8: note: 'local_checker::is_clockwise' declared here
   21 |   bool is_clockwise(int a, int b, int c) {
      |        ^~~~~~~~~~~~
tri.cpp: In function 'int main()':
tri.cpp:60:32: error: 'is_clockwise' was not declared in this scope; did you mean 'local_checker::is_clockwise'?
   60 |       while (sz(temp) >= 2 && !is_clockwise(temp[sz(temp) - 2], temp.back(), i)) temp.pop_back();
      |                                ^~~~~~~~~~~~
      |                                local_checker::is_clockwise
tri.cpp:21:8: note: 'local_checker::is_clockwise' declared here
   21 |   bool is_clockwise(int a, int b, int c) {
      |        ^~~~~~~~~~~~
tri.cpp:73:37: error: 'is_clockwise' was not declared in this scope; did you mean 'local_checker::is_clockwise'?
   73 |         if (sz(side[h ^ i]) >= 2 && is_clockwise(side[h ^ i][sz(side[h ^ i]) - 2], side[h ^ i].back(), side[!(h ^ i)].back()) == i) {
      |                                     ^~~~~~~~~~~~
      |                                     local_checker::is_clockwise
tri.cpp:21:8: note: 'local_checker::is_clockwise' declared here
   21 |   bool is_clockwise(int a, int b, int c) {
      |        ^~~~~~~~~~~~
tri.cpp:81:3: error: 'give_answer' was not declared in this scope; did you mean 'local_checker::give_answer'?
   81 |   give_answer(sz(side[0]) + sz(side[1]));
      |   ^~~~~~~~~~~
      |   local_checker::give_answer
tri.cpp:26:8: note: 'local_checker::give_answer' declared here
   26 |   void give_answer(int s) {
      |        ^~~~~~~~~~~
In file included from /usr/include/c++/9/bits/stl_algobase.h:71,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from tri.cpp:1:
/usr/include/c++/9/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Iterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = main()::<lambda(int, int)>]':
/usr/include/c++/9/bits/stl_algo.h:81:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1920:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1952:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1967:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:4899:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = main()::<lambda(int, int)>]'
tri.cpp:57:6:   required from here
/usr/include/c++/9/bits/predefined_ops.h:143:18: error: void value not ignored as it ought to be
  143 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = int; _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = main()::<lambda(int, int)>]':
/usr/include/c++/9/bits/stl_algo.h:1827:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1854:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1884:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1970:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:4899:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = main()::<lambda(int, int)>]'
tri.cpp:57:6:   required from here
/usr/include/c++/9/bits/predefined_ops.h:215:11: error: void value not ignored as it ought to be
  215 |  { return bool(_M_comp(__val, *__it)); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Value = int; _Compare = main()::<lambda(int, int)>]':
/usr/include/c++/9/bits/stl_heap.h:133:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_val<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_heap.h:237:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_heap.h:342:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1671:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1932:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1947:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1967:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:4899:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = main()::<lambda(int, int)>]'
tri.cpp:57:6:   required from here
/usr/include/c++/9/bits/predefined_ops.h:177:11: error: void value not ignored as it ought to be
  177 |  { return bool(_M_comp(*__it, __val)); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~