| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1065347 | deera | Longest Trip (IOI23_longesttrip) | 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 "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> solve_d3(int N, int D) {
vector<int> res(N);
iota(res.begin(), res.end(), 0);
return res;
}
vector<int> solve_d2(int N, int D) {
queue<int> stops;
for (int i = 1; i < N; i++) stops.push(i);
deque<int> trip = {0};
while (stops.size() > 1) {
int next = stops.front(); stops.pop();
int last = trip.back();
if (are_connected({next}, {last})) {
trip.push_back(next);
} else {
trip.push_back(stops.front()); stops.pop();
trip.push_back(next);
}
}
if (stops.size() == 1) {
int next = stops.front();
int last = trip.back();
if (are_connected({next}, {last})) {
trip.push_back(next);
} else {
trip.push_front(stops.front()); stops.pop();
}
}
vector<int> res;
for (int x : trip) res.push_back(x);
return res;
}
bool CACHE[256][256];
bool COMPD[256][256];
bool connected(int x, int y) {
if (x > y) swap(x, y);
if (COMPD[x][y]) return CACHE[x][y];
bool res = are_connected({x}, {y});
CACHE[x][y] = res;
COMPD[x][y] = true;
return res;
}
vector<int> longest_trip(int N, int D) {
if (D == 3) return solve_d3(N, D);
if (D == 2) return solve_d2(N, D);
// resetting the cache
for (auto &row : CACHE) fill(row, row + 256, 0);
for (auto &row : COMPD) fill(row, row + 256, 0);
deque<int> trip = {0};
set<int> stops;
for (int i = 1; i < N; i++) stops.insert(i);
random_shuffle(stops.begin(), stops.end());
int half = (N / 2) + 1;
int fail = 0;
while (stops.size() > 1) {
for (auto next: stops) {
int a = trip.front(), b = trip.back();
if (connected(a, next)) {
trip.push_front(next);
stops.erase(next);
fail = 0;
continue;
}
if (connected(b, next)) {
trip.push_back(next);
stops.erase(next);
fail = 0;
continue;
}
if (trip.size() >= half) {
break;
}
fail++;
CACHE[a][b] = 1;
CACHE[b][a] = 1;
COMPD[a][b] = 1;
COMPD[b][a] = 1;
if (fail > 100) {
break;
}
}
}
vector<int> res;
for (int x : trip) res.push_back(x);
return res;
}
Compilation message (stderr)
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:89:29: warning: comparison of integer expressions of different signedness: 'std::deque<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
89 | if (trip.size() >= half) {
| ~~~~~~~~~~~~^~~~~~~
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/stl_algo.h: In instantiation of 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = std::_Rb_tree_const_iterator<int>]':
longesttrip.cpp:67:46: required from here
/usr/include/c++/10/bits/stl_algo.h:4593:43: error: no match for 'operator+' (operand types are 'std::_Rb_tree_const_iterator<int>' and 'int')
4593 | for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
| ~~~~~~~~^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from longesttrip.h:1,
from longesttrip.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:508:5: note: candidate: 'template<class _Iterator> constexpr std::reverse_iterator<_Iterator> std::operator+(typename std::reverse_iterator<_Iterator>::difference_type, const std::reverse_iterator<_Iterator>&)'
508 | operator+(typename reverse_iterator<_Iterator>::difference_type __n,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:508:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4593:43: note: mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
4593 | for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
| ~~~~~~~~^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from longesttrip.h:1,
from longesttrip.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1540:5: note: candidate: 'template<class _Iterator> constexpr std::move_iterator<_IteratorL> std::operator+(typename std::move_iterator<_IteratorL>::difference_type, const std::move_iterator<_IteratorL>&)'
1540 | operator+(typename move_iterator<_Iterator>::difference_type __n,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1540:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4593:43: note: mismatched types 'const std::move_iterator<_IteratorL>' and 'int'
4593 | for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
| ~~~~~~~~^~~
In file included 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/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6022:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
6022 | operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6022:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4593:43: note: 'std::_Rb_tree_const_iterator<int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
4593 | for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
| ~~~~~~~~^~~
In file included from /usr/include/c++/10/string:56,
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/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/basic_string.tcc:1160:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
1160 | operator+(const _CharT* __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.tcc:1160:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4593:43: note: mismatched types 'const _CharT*' and 'std::_Rb_tree_const_iterator<int>'
4593 | for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
| ~~~~~~~~^~~
In file included from /usr/include/c++/10/string:56,
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/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/basic_string.tcc:1180:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(_CharT, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
1180 | operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.tcc:1180:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4593:43: note: mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
4593 | for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
| ~~~~~~~~^~~
In file included 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/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6059:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
6059 | operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6059:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4593:43: note: 'std::_Rb_tree_const_iterator<int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
4593 | for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
| ~~~~~~~~^~~
In file included 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/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6075:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, _CharT)'
6075 | operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6075:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4593:43: note: 'std::_Rb_tree_const_iterator<int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
4593 | for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
| ~~~~~~~~^~~
In file included 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/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6087:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
6087 | operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6087:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4593:43: note: 'std::_Rb_tree_const_iterator<int>' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
4593 | for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
| ~~~~~~~~^~~
In file included 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/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6093:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
6093 | operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6093:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4593:43: note: 'std::_Rb_tree_const_iterator<int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
4593 | for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
| ~~~~~~~~^~~
In file included 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/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6099:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
6099 | operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6099:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4593:43: note: 'std::_Rb_tree_const_iterator<int>' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
4593 | for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
| ~~~~~~~~^~~
In file included 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/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6121:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const _CharT*, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
6121 | operator+(const _CharT* __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6121:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4593:43: note: mismatched types 'const _CharT*' and 'std::_Rb_tree_const_iterator<int>'
4593 | for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
| ~~~~~~~~^~~
In file included 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/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6127:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(_CharT, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
6127 | operator+(_CharT __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6127:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4593:43: note: mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
4593 | for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
| ~~~~~~~~^~~
In file included 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/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from longesttrip.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6133:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, const _CharT*)'
6133 | operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6133:5: note: template argument deduc