제출 #672460

#제출 시각아이디문제언어결과실행 시간메모리
672460Eae02Aliens (IOI16_aliens)C++17
컴파일 에러
0 ms0 KiB
#include "aliens.h"   #include <bits/stdc++.h> using namespace std; using ll = __int128_t; #define all(x) begin(x),end(x)   struct Line { mutable ll k, m, p; ll howManyPhotos; bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } }; struct LineContainer : multiset<Line, less<>> { const ll inf = LLONG_MAX; ll div(ll a, ll b) { // floored division return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) { x->p = inf; return false; } if (x->k == y->k) x->p = x->m > y->m ? inf : -inf; else x->p = div(y->m - x->m, x->k - y->k); return x->p >= y->p; } void add(ll k, ll m, ll howManyPhotos) { auto z = insert({k, m, 0, howManyPhotos}), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } pair<ll, ll> query(ll x) { assert(!empty()); auto l = *lower_bound(x); return make_pair(l.k * x + l.m, l.howManyPhotos); } };   long long take_photos(int n, int m, int K, vector<int> r, vector<int> c) { vector<pair<ll, ll>> intvs; for (int i = 0; i < n; i++) { intvs.emplace_back(min(r[i], c[i]), -max(r[i], c[i])); } sort(all(intvs)); vector<pair<ll, ll>> st; for (auto [l, r] : intvs) { if (st.empty() || -r > st.back().second) st.emplace_back(l, -r); } //for (auto [l, r] : st) { // cerr << "intv " << l << " " << r << "\n"; //} auto square = [&] (ll x) { return x * x; }; auto alienTrick = [&] (ll cost) -> pair<ll, ll> { // (ans, howManyPhotos) vector<pair<ll, ll>> dp(st.size() + 1); dp[st.size()] = {0,0}; LineContainer lc; auto addToLC = [&] (ll ie) { if (ie == 0) return; ll ex = st[ie-1].second + 1; ll bx = st[ie].first; ll k = -2 * ex; ll m = dp[ie].first + square(ex) - square(max(ex - bx, (ll)0LL)); lc.add(-k, -m, dp[ie].second); }; for (ll i = (ll)st.size() - 1; i >= 0; i--) { pair<ll, ll> ans = { dp[st.size()].first + square(st.back().second - st[i].first + 1) + cost, -1LL }; /*for (ll ie = i + 1; ie < (ll)st.size(); ie++) { ll ex = st[ie-1].second + 1; ll bx = st[ie].first; ans = min(ans, dp[ie][remk - 1] + square(ex) - 2 * ex * st[i].first + square(st[i].first) - square(max(ex - bx, 0LL)) ); }*/ if (!lc.empty()) { auto lcq = lc.query(st[i].first); ans = min(ans, make_pair(-lcq.first + square(st[i].first) + cost, lcq.second - 1)); } dp[i] = ans; addToLC(i); } return { dp[0].first, -dp[0].second }; }; ll lo = 0; ll hi = 1E9; while (hi > lo) { ll mid = lo + (hi - lo) / 2; auto [ans, howManyPhotos] = alienTrick(mid); if (howManyPhotos > K) lo = mid + 1; else hi = mid; } auto [ans, howManyPhotos] = alienTrick(lo); return ans - lo * K; }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp:2:5: error: extended character   is not valid in an identifier
    2 |      
      |     ^
aliens.cpp:7:5: error: extended character   is not valid in an identifier
    7 |      
      |     ^
aliens.cpp:36:5: error: extended character   is not valid in an identifier
   36 |      
      |     ^
aliens.cpp:2:5: error: '\U000000a0' does not name a type
    2 |      
      |     ^
aliens.cpp:7:5: error: '\U000000a0' does not name a type
    7 |      
      |     ^
aliens.cpp:14:37: error: 'Line' was not declared in this scope
   14 |     struct LineContainer : multiset<Line, less<>> {
      |                                     ^~~~
aliens.cpp:14:48: error: template argument 1 is invalid
   14 |     struct LineContainer : multiset<Line, less<>> {
      |                                                ^~
aliens.cpp:14:48: error: template argument 3 is invalid
aliens.cpp:19:17: error: 'auto' parameter not permitted in this context
   19 |      bool isect(iterator x, iterator y) {
      |                 ^~~~~~~~
aliens.cpp:19:29: error: 'auto' parameter not permitted in this context
   19 |      bool isect(iterator x, iterator y) {
      |                             ^~~~~~~~
aliens.cpp: In member function 'bool LineContainer::isect()':
aliens.cpp:20:11: error: 'y' was not declared in this scope; did you mean 'yn'?
   20 |       if (y == end()) { x->p = inf; return false; }
      |           ^
      |           yn
aliens.cpp:20:20: error: no matching function for call to 'end()'
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
In file included from /usr/include/c++/10/bits/stl_vector.h:63,
                 from /usr/include/c++/10/vector:67,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/initializer_list:101:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)'
  101 |     end(initializer_list<_Tp> __ils) noexcept
      |     ^~~
/usr/include/c++/10/initializer_list:101:5: note:   template argument deduction/substitution failed:
aliens.cpp:20:20: note:   candidate expects 1 argument, 0 provided
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:71:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&)'
   71 |     end(_Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/10/bits/range_access.h:71:5: note:   template argument deduction/substitution failed:
aliens.cpp:20:20: note:   candidate expects 1 argument, 0 provided
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:81:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&)'
   81 |     end(const _Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/10/bits/range_access.h:81:5: note:   template argument deduction/substitution failed:
aliens.cpp:20:20: note:   candidate expects 1 argument, 0 provided
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:100:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
  100 |     end(_Tp (&__arr)[_Nm])
      |     ^~~
/usr/include/c++/10/bits/range_access.h:100:5: note:   template argument deduction/substitution failed:
aliens.cpp:20:20: note:   candidate expects 1 argument, 0 provided
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from aliens.cpp:3:
/usr/include/c++/10/valarray:1234:5: note: candidate: 'template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)'
 1234 |     end(valarray<_Tp>& __va)
      |     ^~~
/usr/include/c++/10/valarray:1234:5: note:   template argument deduction/substitution failed:
aliens.cpp:20:20: note:   candidate expects 1 argument, 0 provided
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from aliens.cpp:3:
/usr/include/c++/10/valarray:1244:5: note: candidate: 'template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
/usr/include/c++/10/valarray:1244:5: note:   template argument deduction/substitution failed:
aliens.cpp:20:20: note:   candidate expects 1 argument, 0 provided
   20 |       if (y == end()) { x->p = inf; return false; }
      |                    ^
aliens.cpp:20:25: error: 'x' was not declared in this scope
   20 |       if (y == end()) { x->p = inf; return false; }
      |                         ^
aliens.cpp:21:11: error: 'x' was not declared in this scope
   21 |       if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
      |           ^
aliens.cpp:21:19: error: 'y' was not declared in this scope; did you mean 'yn'?
   21 |       if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
      |                   ^
      |                   yn
aliens.cpp:23:14: error: 'x' was not declared in this scope
   23 |       return x->p >= y->p;
      |              ^
aliens.cpp:23:22: error: 'y' was not declared in this scope; did you mean 'yn'?
   23 |       return x->p >= y->p;
      |                      ^
      |                      yn
aliens.cpp: In member function 'void LineContainer::add(ll, ll, ll)':
aliens.cpp:26:16: error: 'insert' was not declared in this scope; did you mean 'isect'?
   26 |       auto z = insert({k, m, 0, howManyPhotos}), y = z++, x = y;
      |                ^~~~~~
      |                isect
aliens.cpp:27:20: error: 'y' was not declared in this scope; did you mean 'yn'?
   27 |       while (isect(y, z)) z = erase(z);
      |                    ^
      |                    yn
aliens.cpp:27:31: error: 'erase' was not declared in this scope
   27 |       while (isect(y, z)) z = erase(z);
      |                               ^~~~~
aliens.cpp:28:11: error: 'x' was not declared in this scope
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |           ^
aliens.cpp:28:22: error: no matching function for call to 'begin()'
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
In file included from /usr/include/c++/10/bits/stl_vector.h:63,
                 from /usr/include/c++/10/vector:67,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/initializer_list:90:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
   90 |     begin(initializer_list<_Tp> __ils) noexcept
      |     ^~~~~
/usr/include/c++/10/initializer_list:90:5: note:   template argument deduction/substitution failed:
aliens.cpp:28:22: note:   candidate expects 1 argument, 0 provided
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:51:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&)'
   51 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:51:5: note:   template argument deduction/substitution failed:
aliens.cpp:28:22: note:   candidate expects 1 argument, 0 provided
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:61:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&)'
   61 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note:   template argument deduction/substitution failed:
aliens.cpp:28:22: note:   candidate expects 1 argument, 0 provided
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:90:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])'
   90 |     begin(_Tp (&__arr)[_Nm])
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note:   template argument deduction/substitution failed:
aliens.cpp:28:22: note:   candidate expects 1 argument, 0 provided
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from aliens.cpp:3:
/usr/include/c++/10/valarray:1214:5: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
 1214 |     begin(valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/10/valarray:1214:5: note:   template argument deduction/substitution failed:
aliens.cpp:28:22: note:   candidate expects 1 argument, 0 provided
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from aliens.cpp:3:
/usr/include/c++/10/valarray:1224:5: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/10/valarray:1224:5: note:   template argument deduction/substitution failed:
aliens.cpp:28:22: note:   candidate expects 1 argument, 0 provided
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                      ^
aliens.cpp:28:38: error: 'y' was not declared in this scope; did you mean 'yn'?
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                                      ^
      |                                      yn
aliens.cpp:28:55: error: 'erase' was not declared in this scope
   28 |       if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                                                       ^~~~~
aliens.cpp:29:15: error: 'y' was not declared in this scope; did you mean 'yn'?
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |               ^
      |               yn
aliens.cpp:29:19: error: 'x' was not declared in this scope
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                   ^
aliens.cpp:29:31: error: no matching function for call to 'begin()'
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
In file included from /usr/include/c++/10/bits/stl_vector.h:63,
                 from /usr/include/c++/10/vector:67,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/initializer_list:90:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
   90 |     begin(initializer_list<_Tp> __ils) noexcept
      |     ^~~~~
/usr/include/c++/10/initializer_list:90:5: note:   template argument deduction/substitution failed:
aliens.cpp:29:31: note:   candidate expects 1 argument, 0 provided
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:51:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&)'
   51 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:51:5: note:   template argument deduction/substitution failed:
aliens.cpp:29:31: note:   candidate expects 1 argument, 0 provided
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:61:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&)'
   61 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note:   template argument deduction/substitution failed:
aliens.cpp:29:31: note:   candidate expects 1 argument, 0 provided
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:90:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])'
   90 |     begin(_Tp (&__arr)[_Nm])
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note:   template argument deduction/substitution failed:
aliens.cpp:29:31: note:   candidate expects 1 argument, 0 provided
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from aliens.cpp:3:
/usr/include/c++/10/valarray:1214:5: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
 1214 |     begin(valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/10/valarray:1214:5: note:   template argument deduction/substitution failed:
aliens.cpp:29:31: note:   candidate expects 1 argument, 0 provided
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from aliens.cpp:3:
/usr/include/c++/10/valarray:1224:5: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/10/valarray:1224:5: note:   template argument deduction/substitution failed:
aliens.cpp:29:31: note:   candidate expects 1 argument, 0 provided
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                               ^
aliens.cpp:29:63: error: 'erase' was not declared in this scope
   29 |       while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                                                               ^~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from aliens.cpp:3:
aliens.cpp: In member function 'std::pair<__int128, __int128> LineContainer::query(ll)':
aliens.cpp:31:47: error: no matching function for call to 'empty()'
   31 |      pair<ll, ll> query(ll x) { assert(!empty());
      |                                               ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:263:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.empty()) std::empty(const _Container&)'
  263 |     empty(const _Container& __cont) noexcept(noexcept(__cont.empty()))
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:263:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from aliens.cpp:3:
aliens.cpp:31:47: note:   candidate expects 1 argument, 0 provided
   31 |      pair<ll, ll> query(ll x) { assert(!empty());
      |                                               ^
In file included from /usr/include/c++/10/vector:69,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/10/bits/range_access.h:272:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr bool std::empty(const _Tp (&)[_Nm])'
  272 |     empty(const _Tp (&)[_Nm]) noexcept
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:272:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_6