| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 592881 | yanndev | Wiring (IOI17_wiring) | 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 "wiring.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1;
const ll oo = 1e18;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
struct pt {
int x;
bool col;
};
vector<pt> pts;
while(!r.empty() or !b.empty()) {
if(!r.empty()) {
pts.push_back({r.back(),1});
r.pop_back();
} else {
pts.push_back({b.back(),0});
b.pop_back();
}
}
sort(all(pts));
int n = pts.size();
pts.insert(pts.begin(),{0,0});
vector<ll> pref(n+2);
for(int i=0;i<=n;++i) {
pref[i+1]=pref[i]+pts[i].x;
}
vector<ll> dp(n+1,oo);
dp[0]=0;
auto cost = [&](int a, int b, int c) {
int bal = (b-a)-(c-b);
ll tmp=0;
if(bal>0) tmp = (ll)pts[b].x*bal;
else tmp = (ll)pts[b-1].x*bal;
return tmp + min(dp[a],dp[a-1]) + pref[c] - pref[b] - (pref[b]-pref[a]);
};
int last=-1;
for(int i=1;i<=n;) {
int j=i;
while(j<=n and pts[i].col==pts[j].col)
++j;
if(last!=-1) {
for(int k=j;k>i;--k) {
while(last<i-1 and cost(last+1,i,k)<cost(last,i,k)) {
++last;
}
// for(int o=last;o<i;++o) dp[k-1] =min(dp[k-1],cost(o,i,k));
dp[k-1] =min(dp[k-1],cost(last,i,k));
}
}
last = i;
i=j;
}
return dp[n];
}
Compilation message (stderr)
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Iterator2 = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >]':
/usr/include/c++/10/bits/stl_algo.h:82:17: required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1924:34: required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1958:38: required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1974:25: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:4859:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >]'
wiring.cpp:31:15: required from here
/usr/include/c++/10/bits/predefined_ops.h:43:23: error: no match for 'operator<' (operand types are 'min_total_length(std::vector<int>, std::vector<int>)::pt' and 'min_total_length(std::vector<int>, std::vector<int>)::pt')
43 | { return *__it1 < *__it2; }
| ~~~~~~~^~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)'
1096 | operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:43:23: note: 'min_total_length(std::vector<int>, std::vector<int>)::pt' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
43 | { return *__it1 < *__it2; }
| ~~~~~~~^~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)'
1104 | operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:43:23: note: 'min_total_length(std::vector<int>, std::vector<int>)::pt' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
43 | { return *__it1 < *__it2; }
| ~~~~~~~^~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_less_iter::operator()(_Value&, _Iterator) const [with _Value = min_total_length(std::vector<int>, std::vector<int>)::pt; _Iterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >]':
/usr/include/c++/10/bits/stl_algo.h:1826:20: required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Compare = __gnu_cxx::__ops::_Val_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1854:36: required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1886:25: required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1977:31: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:4859:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >]'
wiring.cpp:31:15: required from here
/usr/include/c++/10/bits/predefined_ops.h:96:22: error: no match for 'operator<' (operand types are 'min_total_length(std::vector<int>, std::vector<int>)::pt' and 'min_total_length(std::vector<int>, std::vector<int>)::pt')
96 | { return __val < *__it; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)'
1096 | operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note: 'min_total_length(std::vector<int>, std::vector<int>)::pt' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
96 | { return __val < *__it; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)'
1104 | operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note: 'min_total_length(std::vector<int>, std::vector<int>)::pt' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
96 | { return __val < *__it; }
| ~~~~~~^~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_less_val::operator()(_Iterator, _Value&) const [with _Iterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Value = min_total_length(std::vector<int>, std::vector<int>)::pt]':
/usr/include/c++/10/bits/stl_heap.h:139:48: required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Distance = long int; _Tp = min_total_length(std::vector<int>, std::vector<int>)::pt; _Compare = __gnu_cxx::__ops::_Iter_less_val]'
/usr/include/c++/10/bits/stl_heap.h:246:23: required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Distance = long int; _Tp = min_total_length(std::vector<int>, std::vector<int>)::pt; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_heap.h:355:22: required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1666:23: required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1937:25: required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1953:27: required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1974:25: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:4859:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<min_total_length(std::vector<int>, std::vector<int>)::pt*, std::vector<min_total_length(std::vector<int>, std::vector<int>)::pt> >]'
wiring.cpp:31:15: required from here
/usr/include/c++/10/bits/predefined_ops.h:67:22: error: no match for 'operator<' (operand types are 'min_total_length(std::vector<int>, std::vector<int>)::pt' and 'min_total_length(std::vector<int>, std::vector<int>)::pt')
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)'
1096 | operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'min_total_length(std::vector<int>, std::vector<int>)::pt' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)'
1104 | operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/vector:60,
from wiring.h:1,
from wiring.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'min_total_length(std::vector<int>, std::vector<int>)::pt' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~