Submission #1014770

#TimeUsernameProblemLanguageResultExecution timeMemory
1014770Ausp3xRoller Coaster Railroad (IOI16_railroad)C++17
Compilation error
0 ms0 KiB
// 人外有人，天外有天
// author: Ausp3x

// #pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "railroad.h"
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
// #define DEBUG
typedef long long             lng;
typedef pair<int, int>        pi;
typedef vector<int>           vi;
typedef pair<lng, lng>        pl;
typedef vector<lng, lng>      vl;

int const INF32 = 0x3f3f3f3f;
lng const INF64 = 0x3f3f3f3f3f3f3f3f;

lng plan_roller_coaster(vi s, vi t) {
    int n = s.size();
    
    if (n <= 16) {
        vector<vi> cnts(n + 1);
        for (int i = 0; i < (1 << n); i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++)
                if (i & (1 << j))
                    cnt++;

            cnts[cnt].push_back(i);
        }

        vector<vl> dp(1 << n, vl(n, INF64));
        for (int i = 0; i < n; i++) 
            dp[1 << i][i] = 0;
        for (int i = 2; i <= n; i++)
            for (int x : cnts[i])
                for (int j = 0; j < n; j++) {
                    if (!(x & (1 << j)))
                        continue;

                    for (int k = 0; k < n; k++)
                        if ((x & (1 << k)) && k != j)
                            dp[x][j] = min(dp[x][j], dp[x ^ (1 << j)][k] + max(s[j] - t[k], 0))
                }
    
        lng ans = INF64;
        for (int i = 0; i < n; i++)
            ans = min(ans, dp[(1 << n) - 1][i]);
        return ans;
    }
    
    return -1;
}

#ifdef DEBUG
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    cin >> t;
    while (t--) {
        solve(t);
    }

    return 0;
}
#endif

Compilation message (stderr)

In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from railroad.cpp:5:
/usr/include/c++/10/bits/stl_vector.h: In instantiation of 'struct std::_Vector_base<long long int, long long int>':
/usr/include/c++/10/bits/stl_vector.h:389:11:   required from 'class std::vector<long long int, long long int>'
railroad.cpp:38:42:   required from here
/usr/include/c++/10/bits/stl_vector.h:87:21: error: 'long long int' is not a class, struct, or union type
   87 |  rebind<_Tp>::other _Tp_alloc_type;
      |                     ^~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:89:9: error: 'long long int' is not a class, struct, or union type
   89 |         pointer;
      |         ^~~~~~~
/usr/include/c++/10/bits/stl_vector.h: In instantiation of 'class std::vector<long long int, long long int>':
railroad.cpp:38:42:   required from here
/usr/include/c++/10/bits/stl_vector.h:404:64: error: 'long long int' is not a class, struct, or union type
  404 |       static_assert(is_same<typename _Alloc::value_type, _Tp>::value,
      |                                                                ^~~~~
/usr/include/c++/10/bits/stl_vector.h:474:20: error: '_M_allocate' has not been declared in 'std::_Base<long long int, long long int>'
  474 |       using _Base::_M_allocate;
      |                    ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:475:20: error: '_M_deallocate' has not been declared in 'std::_Base<long long int, long long int>'
  475 |       using _Base::_M_deallocate;
      |                    ^~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:477:20: error: '_M_get_Tp_allocator' has not been declared in 'std::_Base<long long int, long long int>'
  477 |       using _Base::_M_get_Tp_allocator;
      |                    ^~~~~~~~~~~~~~~~~~~
railroad.cpp: In function 'lng plan_roller_coaster(vi, vi)':
railroad.cpp:38:42: error: call of overloaded 'vector(int&, const lng&)' is ambiguous
   38 |         vector<vl> dp(1 << n, vl(n, INF64));
      |                                          ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from railroad.cpp:5:
/usr/include/c++/10/bits/stl_vector.h:522:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const value_type&, const allocator_type&) [with _Tp = long long int; _Alloc = long long int; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = long long int; std::vector<_Tp, _Alloc>::allocator_type = long long int]'
  522 |       vector(size_type __n, const value_type& __value,
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:510:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const allocator_type&) [with _Tp = long long int; _Alloc = long long int; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::allocator_type = long long int]'
  510 |       vector(size_type __n, const allocator_type& __a = allocator_type())
      |       ^~~~~~
railroad.cpp:40:23: error: no match for 'operator[]' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int, long long int> >, std::vector<long long int, long long int> >::value_type' {aka 'std::vector<long long int, long long int>'} and 'int')
   40 |             dp[1 << i][i] = 0;
      |                       ^
railroad.cpp:49:34: error: no match for 'operator[]' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int, long long int> >, std::vector<long long int, long long int> >::value_type' {aka 'std::vector<long long int, long long int>'} and 'int')
   49 |                             dp[x][j] = min(dp[x][j], dp[x ^ (1 << j)][k] + max(s[j] - t[k], 0))
      |                                  ^
railroad.cpp:49:49: error: no match for 'operator[]' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int, long long int> >, std::vector<long long int, long long int> >::value_type' {aka 'std::vector<long long int, long long int>'} and 'int')
   49 |                             dp[x][j] = min(dp[x][j], dp[x ^ (1 << j)][k] + max(s[j] - t[k], 0))
      |                                                 ^
railroad.cpp:49:70: error: no match for 'operator[]' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int, long long int> >, std::vector<long long int, long long int> >::value_type' {aka 'std::vector<long long int, long long int>'} and 'int')
   49 |                             dp[x][j] = min(dp[x][j], dp[x ^ (1 << j)][k] + max(s[j] - t[k], 0))
      |                                                                      ^
railroad.cpp:54:44: error: no match for 'operator[]' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int, long long int> >, std::vector<long long int, long long int> >::value_type' {aka 'std::vector<long long int, long long int>'} and 'int')
   54 |             ans = min(ans, dp[(1 << n) - 1][i]);
      |                                            ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from railroad.cpp:5:
/usr/include/c++/10/bits/stl_vector.h: In instantiation of 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = long long int; _Alloc = long long int]':
/usr/include/c++/10/bits/stl_construct.h:140:22:   required from 'constexpr void std::_Destroy(_Tp*) [with _Tp = std::vector<long long int, long long int>]'
/usr/include/c++/10/bits/stl_construct.h:152:19:   required from 'static void std::_Destroy_aux<<anonymous> >::__destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::vector<long long int, long long int>*; bool <anonymous> = false]'
/usr/include/c++/10/bits/stl_construct.h:185:11:   required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::vector<long long int, long long int>*]'
/usr/include/c++/10/bits/alloc_traits.h:738:15:   required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = std::vector<long long int, long long int>*; _Tp = std::vector<long long int, long long int>]'
/usr/include/c++/10/bits/stl_vector.h:680:15:   required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::vector<long long int, long long int>; _Alloc = std::allocator<std::vector<long long int, long long int> >]'
railroad.cpp:38:43:   required from here
/usr/include/c++/10/bits/stl_vector.h:680:30: error: 'struct std::_Vector_base<long long int, long long int>::_Vector_impl' has no member named '_M_start'
  680 |  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
      |                ~~~~~~~~~~~~~~^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:680:54: error: 'struct std::_Vector_base<long long int, long long int>::_Vector_impl' has no member named '_M_finish'
  680 |  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
      |                                        ~~~~~~~~~~~~~~^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:681:28: error: '_M_get_Tp_allocator' was not declared in this scope; did you mean 'get_allocator'?
  681 |         _M_get_Tp_allocator());
      |         ~~~~~~~~~~~~~~~~~~~^~
      |         get_allocator
/usr/include/c++/10/bits/stl_vector.h: In instantiation of 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = long long int; _Alloc = long long int]':
/usr/include/c++/10/bits/stl_vector.h:683:7:   required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = long long int; _Alloc = long long int]'
/usr/include/c++/10/bits/stl_construct.h:140:22:   required from 'constexpr void std::_Destroy(_Tp*) [with _Tp = std::vector<long long int, long long int>]'
/usr/include/c++/10/bits/stl_construct.h:152:19:   required from 'static void std::_Destroy_aux<<anonymous> >::__destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::vector<long long int, long long int>*; bool <anonymous> = false]'
/usr/include/c++/10/bits/stl_construct.h:185:11:   required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::vector<long long int, long long int>*]'
/usr/include/c++/10/bits/alloc_traits.h:738:15:   required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = std::vector<long long int, long long int>*; _Tp = std::vector<long long int, long long int>]'
/usr/include/c++/10/bits/stl_vector.h:680:15:   required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::vector<long long int, long long int>; _Alloc = std::allocator<std::vector<long long int, long long int> >]'
railroad.cpp:38:43:   required from here
/usr/include/c++/10/bits/stl_vector.h:335:24: error: 'struct std::_Vector_base<long long int, long long int>::_Vector_impl' has no member named '_M_start'
  335 |  _M_deallocate(_M_impl._M_start,
      |                ~~~~~~~~^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:336:17: error: 'struct std::_Vector_base<long long int, long long int>::_Vector_impl' has no member named '_M_end_of_storage'
  336 |         _M_impl._M_end_of_storage - _M_impl._M_start);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:336:45: error: 'struct std::_Vector_base<long long int, long long int>::_Vector_impl' has no member named '_M_start'
  336 |         _M_impl._M_end_of_storage - _M_impl._M_start);
      |                                     ~~~~~~~~^~~~~~~~