| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 625044 | MilosMilutinovic | 순열 (APIO22_perm) | C++17 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "perm.h"
using namespace std;
long long Count(vector<int> p) {
int n = p.size();
vector<long long> dp(n);
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (p[j] < p[i]) {
dp[i] += dp[j];
}
}
}
long long cnt = 1;
for (int i = 0; i < n; i++) {
cnt += dp[i];
}
return cnt;
}
vector<int> construct_permutation(long long k) {
if (k <= 90) {
vector<int> ans;
for (int i = k - 2; i >= 0; i--) {
ans.push_back(i);
}
return ans;
}
for (int len = 1; len <= 90; len++) {
vector<int> perm(len);
for (int i = 0; i < len; i++) {
perm[i] = i;
}
if (Count(perm) < k) {
continue;
}
reverse(perm.begin(), perm.end());
long long total = Count(perm);
do {
vector<tuple<long long, int, int>> c;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
swap(perm[i], perm[j]);
c.emplace_back(Count(perm) - total, i, j);
swap(perm[i], perm[j]);
}
}
sort(c.begin(), c.end());
tuple<long long, int, int> f = make_tuple(-1, -1, -1);
for (auto& p : c) {
if (get<0>(p) > 0 && total + get<0>(p) <= k) {
f = p;
}
}
if (get<0>(f) == -1) {
break;
}
total += get<0>(f);
swap(perm[get<1>(f)], perm[get<2>(f)]);
} while (total < k);
if (total == k) {
return perm;
}
}
return vector<int>(1, 0);
}
Compilation message (stderr)
perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:39:5: error: 'reverse' was not declared in this scope
39 | reverse(perm.begin(), perm.end());
| ^~~~~~~
perm.cpp:50:7: error: 'sort' was not declared in this scope; did you mean 'short'?
50 | sort(c.begin(), c.end());
| ^~~~
| short
perm.cpp:51:34: error: variable 'std::tuple<long long int, int, int> f' has initializer but incomplete type
51 | tuple<long long, int, int> f = make_tuple(-1, -1, -1);
| ^
perm.cpp:51:38: error: 'make_tuple' was not declared in this scope
51 | tuple<long long, int, int> f = make_tuple(-1, -1, -1);
| ^~~~~~~~~~
perm.cpp:2:1: note: 'std::make_tuple' is defined in header '<tuple>'; did you forget to '#include <tuple>'?
1 | #include "perm.h"
+++ |+#include <tuple>
2 |
perm.cpp:53:13: error: 'get' was not declared in this scope
53 | if (get<0>(p) > 0 && total + get<0>(p) <= k) {
| ^~~
perm.cpp:57:11: error: 'get' was not declared in this scope
57 | if (get<0>(f) == -1) {
| ^~~
perm.cpp:60:16: error: 'get' was not declared in this scope
60 | total += get<0>(f);
| ^~~
In file included from /usr/include/c++/10/vector:67,
from perm.h:1,
from perm.cpp:1:
/usr/include/c++/10/bits/stl_vector.h: In instantiation of 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = std::tuple<long long int, int, int>; _Alloc = std::allocator<std::tuple<long long int, int, int> >]':
/usr/include/c++/10/bits/stl_vector.h:487:7: required from here
/usr/include/c++/10/bits/stl_vector.h:336:35: error: invalid use of incomplete type 'class std::tuple<long long int, int, int>'
336 | _M_impl._M_end_of_storage - _M_impl._M_start);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from perm.h:1,
from perm.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: declaration of 'class std::tuple<long long int, int, int>'
2631 | class tuple;
| ^~~~~
/usr/include/c++/10/type_traits: In instantiation of 'struct std::is_nothrow_constructible<std::tuple<long long int, int, int>, long long int, int&, int&>':
/usr/include/c++/10/bits/alloc_traits.h:509:57: required from 'static void std::allocator_traits<std::allocator<_Tp1> >::construct(std::allocator_traits<std::allocator<_Tp1> >::allocator_type&, _Up*, _Args&& ...) [with _Up = std::tuple<long long int, int, int>; _Args = {long long int, int&, int&}; _Tp = std::tuple<long long int, int, int>; std::allocator_traits<std::allocator<_Tp1> >::allocator_type = std::allocator<std::tuple<long long int, int, int> >]'
/usr/include/c++/10/bits/vector.tcc:115:30: required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {long long int, int&, int&}; _Tp = std::tuple<long long int, int, int>; _Alloc = std::allocator<std::tuple<long long int, int, int> >; std::vector<_Tp, _Alloc>::reference = std::tuple<long long int, int, int>&]'
perm.cpp:46:51: required from here
/usr/include/c++/10/type_traits:1011:52: error: static assertion failed: template argument must be a complete class or an unbounded array
1011 | static_assert(std::__is_complete_or_unbounded(__type_identity<_Tp>{}),
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/vector:72,
from perm.h:1,
from perm.cpp:1:
/usr/include/c++/10/bits/vector.tcc: In instantiation of 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {long long int, int&, int&}; _Tp = std::tuple<long long int, int, int>; _Alloc = std::allocator<std::tuple<long long int, int, int> >; std::vector<_Tp, _Alloc>::reference = std::tuple<long long int, int, int>&]':
perm.cpp:46:51: required from here
/usr/include/c++/10/bits/vector.tcc:117:22: error: cannot increment a pointer to incomplete type 'std::tuple<long long int, int, int>'
117 | ++this->_M_impl._M_finish;
| ~~~~~~~~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from perm.h:1,
from perm.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h: In instantiation of '__gnu_cxx::__normal_iterator<_Iterator, _Container>& __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator++() [with _Iterator = std::tuple<long long int, int, int>*; _Container = std::vector<std::tuple<long long int, int, int> >]':
perm.cpp:52:22: required from here
/usr/include/c++/10/bits/stl_iterator.h:980:4: error: cannot increment a pointer to incomplete type 'std::tuple<long long int, int, int>'
980 | ++_M_current;
| ^~~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from perm.h:1,
from perm.cpp:1:
/usr/include/c++/10/type_traits: In instantiation of 'struct std::is_destructible<std::tuple<long long int, int, int> >':
/usr/include/c++/10/bits/stl_construct.h:177:51: required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::tuple<long long int, int, int>*]'
/usr/include/c++/10/bits/alloc_traits.h:738:15: required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = std::tuple<long long int, int, int>*; _Tp = std::tuple<long long int, int, int>]'
/usr/include/c++/10/bits/stl_vector.h:680:15: required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::tuple<long long int, int, int>; _Alloc = std::allocator<std::tuple<long long int, int, int> >]'
perm.cpp:42:42: required from here
/usr/include/c++/10/type_traits:844:52: error: static assertion failed: template argument must be a complete class or an unbounded array
844 | static_assert(std::__is_complete_or_unbounded(__type_identity<_Tp>{}),
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/vector:65,
from perm.h:1,
from perm.cpp:1:
/usr/include/c++/10/bits/stl_construct.h: In instantiation of 'void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::tuple<long long int, int, int>*]':
/usr/include/c++/10/bits/alloc_traits.h:738:15: required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = std::tuple<long long int, int, int>*; _Tp = std::tuple<long long int, int, int>]'
/usr/include/c++/10/bits/stl_vector.h:680:15: required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::tuple<long long int, int, int>; _Alloc = std::allocator<std::tuple<long long int, int, int> >]'
perm.cpp:42:42: required from here
/usr/include/c++/10/bits/stl_construct.h:177:51: error: static assertion failed: value type is destructible
177 | static_assert(is_destructible<_Value_type>::value,
| ^~~~~
/usr/include/c++/10/bits/stl_construct.h:184:25: error: invalid use of incomplete type 'std::iterator_traits<std::tuple<long long int, int, int>*>::value_type' {aka 'class std::tuple<long long int, int, int>'}
184 | std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from perm.h:1,
from perm.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: declaration of 'std::iterator_traits<std::tuple<long long int, int, int>*>::value_type' {aka 'class std::tuple<long long int, int, int>'}
2631 | class tuple;
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
from /usr/include/c++/10/bits/allocator.h:46,
from /usr/include/c++/10/vector:64,
from perm.h:1,
from perm.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::deallocate(_Tp*, __gnu_cxx::new_allocator<_Tp>::size_type) [with _Tp = std::tuple<long long int, int, int>; __gnu_cxx::new_allocator<_Tp>::size_type = long unsigned int]':
/usr/include/c++/10/bits/alloc_traits.h:492:23: required from 'static void std::allocator_traits<std::allocator<_Tp1> >::deallocate(std::allocator_traits<std::allocator<_Tp1> >::allocator_type&, std::allocator_traits<std::allocator<_Tp1> >::pointer, std::allocator_traits<std::allocator<_Tp1> >::size_type) [with _Tp = std::tuple<long long int, int, int>; std::allocator_traits<std::allocator<_Tp1> >::allocator_type = std::allocator<std::tuple<long long int, int, int> >; std::allocator_traits<std::allocator<_Tp1> >::pointer = std::tuple<long long int, int, int>*; std::allocator_traits<std::allocator<_Tp1> >::size_type = long unsigned int]'
/usr/include/c++/10/bits/stl_vector.h:354:19: required from 'void std::_Vector_base<_Tp, _Alloc>::_M_deallocate(std::_Vector_base<_Tp, _Alloc>::pointer, std::size_t) [with _Tp = std::tuple<long long int, int, int>; _Alloc = std::allocator<std::tuple<long long int, int, int> >; std::_Vector_base<_Tp, _Alloc>::pointer = std::tuple<long long int, int, int>*; std::size_t = long unsigned int]'
/usr/include/c++/10/bits/stl_vector.h:335:2: required from 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = std::tuple<long long int, int, int>; _Alloc = std::allocator<std::tuple<long long int, int, int> >]'
/usr/include/c++/10/bits/stl_vector.h:487:7: required from here
/usr/include/c++/10/ext/new_allocator.h:123:6: error: invalid application of '__alignof__' to incomplete type 'std::tuple<long long int, int, int>'
123 | if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
| ^~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:127:16: error: invalid application of 'sizeof' to incomplete type 'std::tuple<long long int, int, int>'
127 | __t * sizeof(_Tp),
| ^~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:129:27: error: invalid application of '__alignof__' to incomplete type 'std::tuple<long long int, int, int>'
129 | std::align_val_t(alignof(_Tp)));
| ^~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:135:14: error: invalid application of 'sizeof' to incomplete type 'std::tuple<long long int, int, int>'
135 | , __t * sizeof(_Tp)
| ^~~~~~~~~~~