| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 287450 | Namnamseo | Teams (CEOI11_tea) | 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
const int max_n = int(1e6) + 10, inf = 1e9;
typedef pair<int,int> pp;
pp data[max_n];
int n;
int dpTN[max_n];
int dpMX[max_n];
struct indi {
int team_num;
int max_size;
int from;
indi(int a=-1, int b=inf, int c=-1){
team_num = a; max_size = b; from = c;
}
bool operator<(const indi& r) const {
return make_pair(team_num, -max_size) <
make_pair(r.team_num, -r.max_size);
}
};
const int M =1048576;
indi tree[M<<1];
indi tree_add[M<<1];
indi dp[max_n];
int bef[max_n];
indi getMax(indi* tree, int p){
indi ret;
p+=M;
while(p) ret=max(ret, tree[p]), p>>=1;
return ret;
}
void upd(indi* tree, int l, int r, indi val){
l+=M; r+=M;
while(l<=r){
if(l%2==1) tree[l]=max(tree[l], val), ++l;
if(r%2==0) tree[r]=max(tree[r], val), --r;
l>>=1; r>>=1;
}
}
vector<vector<int>> ans;
struct cmp {
bool operator()(const int& a, const int& b){
return ans[a].size() > ans[b].size();
}
};
priority_queue<int,vector<int>,cmp> PQ;
int main()
{
read(n);
for(int i=1; i<=n; ++i){
read(data[i].first); data[i].second=i;
}
sort(data+1, data+n+1, greater<pp>());
for(int i=0; i<=n; ++i){
indi v1 = getMax(tree, i);
indi v2 = getMax(tree_add, i);
v2.max_size += i;
indi my = max(v1, v2);
if(i == 0) my = indi(0, 0, -1);
dp[i] = my;
bef[i] = my.from;
if(i == n) break;
if(my.team_num == -1) continue;
int tn = my.team_num;
int mt = my.max_size;
ll pt = tn * 1LL * mt;
int mv=data[i+1].first;
upd(tree, i+1, min(pt, ll(n)), indi(tn, mt, -i));
upd(tree, i+mv, min(i+mt-1, n), indi(tn+1, mt, i));
upd(tree_add, i+max(mv, mt), n, indi(tn+1, -i, i));
}
printf("%d\n", dp[n].team_num);
vector<pp> pend;
int p=n;
while(p){
int x=bef[p];
if(x < 0){
x=-x;
for(int i=x+1; i<=p; ++i){
pend.pb(pp{int(ans.size()), data[i].second});
}
} else {
vector<int> v;
for(int i=x+1; i<=p; ++i){
v.pb(data[i].second);
}
ans.pb(v);
}
p=x;
}
int an=ans.size();
for(int i=an-1; i>=0; --i){
PQ.push(i);
while(pend.size()){
int x, y;
tie(x, y) = pend.back();
if(x != i) break;
pend.pop_back();
int p=PQ.top(); PQ.pop();
ans[p].pb(y);
PQ.push(p);
}
}
for(auto& tmp:ans){
printf("%d ", int(tmp.size()));
for(int x:tmp) printf("%d ", x);
putchar(10);
}
return 0;
}
Compilation message (stderr)
tea.cpp: In function 'int main()':
tea.cpp:68:8: error: reference to 'data' is ambiguous
68 | read(data[i].first); data[i].second=i;
| ^~~~
In file included from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from tea.cpp:1:
/usr/include/c++/9/bits/range_access.h:318:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
318 | data(initializer_list<_Tp> __il) noexcept
| ^~~~
/usr/include/c++/9/bits/range_access.h:309:5: note: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
309 | data(_Tp (&__array)[_Nm]) noexcept
| ^~~~
/usr/include/c++/9/bits/range_access.h:299:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
299 | data(const _Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
/usr/include/c++/9/bits/range_access.h:289:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
289 | data(_Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
tea.cpp:14:4: note: 'pp data [1000010]'
14 | pp data[max_n];
| ^~~~
tea.cpp:68:24: error: reference to 'data' is ambiguous
68 | read(data[i].first); data[i].second=i;
| ^~~~
In file included from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from tea.cpp:1:
/usr/include/c++/9/bits/range_access.h:318:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
318 | data(initializer_list<_Tp> __il) noexcept
| ^~~~
/usr/include/c++/9/bits/range_access.h:309:5: note: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
309 | data(_Tp (&__array)[_Nm]) noexcept
| ^~~~
/usr/include/c++/9/bits/range_access.h:299:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
299 | data(const _Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
/usr/include/c++/9/bits/range_access.h:289:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
289 | data(_Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
tea.cpp:14:4: note: 'pp data [1000010]'
14 | pp data[max_n];
| ^~~~
tea.cpp:70:10: error: reference to 'data' is ambiguous
70 | sort(data+1, data+n+1, greater<pp>());
| ^~~~
In file included from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from tea.cpp:1:
/usr/include/c++/9/bits/range_access.h:318:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
318 | data(initializer_list<_Tp> __il) noexcept
| ^~~~
/usr/include/c++/9/bits/range_access.h:309:5: note: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
309 | data(_Tp (&__array)[_Nm]) noexcept
| ^~~~
/usr/include/c++/9/bits/range_access.h:299:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
299 | data(const _Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
/usr/include/c++/9/bits/range_access.h:289:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
289 | data(_Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
tea.cpp:14:4: note: 'pp data [1000010]'
14 | pp data[max_n];
| ^~~~
tea.cpp:70:18: error: reference to 'data' is ambiguous
70 | sort(data+1, data+n+1, greater<pp>());
| ^~~~
In file included from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from tea.cpp:1:
/usr/include/c++/9/bits/range_access.h:318:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
318 | data(initializer_list<_Tp> __il) noexcept
| ^~~~
/usr/include/c++/9/bits/range_access.h:309:5: note: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
309 | data(_Tp (&__array)[_Nm]) noexcept
| ^~~~
/usr/include/c++/9/bits/range_access.h:299:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
299 | data(const _Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
/usr/include/c++/9/bits/range_access.h:289:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
289 | data(_Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
tea.cpp:14:4: note: 'pp data [1000010]'
14 | pp data[max_n];
| ^~~~
tea.cpp:84:10: error: reference to 'data' is ambiguous
84 | int mv=data[i+1].first;
| ^~~~
In file included from /usr/include/c++/9/string:54,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from tea.cpp:1:
/usr/include/c++/9/bits/range_access.h:318:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
318 | data(initializer_list<_Tp> __il) noexcept
| ^~~~
/usr/include/c++/9/bits/range_access.h:309:5: note: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
309 | data(_Tp (&__array)[_Nm]) noexcept
| ^~~~
/usr/include/c++/9/bits/range_access.h:299:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
299 | data(const _Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
/usr/include/c++/9/bits/range_access.h:289:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
289 | data(_Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
tea.cpp:14:4: note: 'pp data [1000010]'
14 | pp data[max_n];
| ^~~~
tea.cpp:99:47: error: no matching function for call to 'std::pair<int, int>::pair(<brace-enclosed initializer list>)'
99 | pend.pb(pp{int(ans.size()), data[i].second});
| ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from tea.cpp:1:
/usr/include/c++/9/bits/stl_pair.h:436:9: note: candidate: 'template<class ... _Args1, long unsigned int ..._Indexes1, class ... _Args2, long unsigned int ..._Indexes2> std::pair<_T1, _T2>::pair(std::tuple<_Args1 ...>&, std::tuple<_Args2 ...>&, std::_Index_tuple<_Indexes1 ...>, std::_Index_tuple<_Indexes2 ...>)'
436 | pair(tuple<_Args1...>&, tuple<_Args2...>&,
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:436:9: note: template argument deduction/substitution failed:
tea.cpp:99:47: note: mismatched types 'std::tuple<_Tps ...>' and 'int'
99 | pend.pb(pp{int(ans.size()), data[i].second});
| ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from tea.cpp:1:
/usr/include/c++/9/bits/stl_pair.h:375:9: note: candidate: 'template<class ... _Args1, class ... _Args2> std::pair<_T1, _T2>::pair(std::piecewise_construct_t, std::tuple<_Args1 ...>, std::tuple<_Args2 ...>)'
375 | pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>);
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:375:9: note: template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_pair.h:370:21: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(std::_PCC<((! std::is_same<int, _U1>::value) || (! std::is_same<int, _U2>::value)), int, int>::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<((! std::is_same<int, _U1>::value) || (! std::is_same<int, _U2>::value)), int, int>::_ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&)'
370 | explicit constexpr pair(pair<_U1, _U2>&& __p)
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:370:21: note: template argument deduction/substitution failed:
tea.cpp:99:47: note: mismatched types 'std::pair<_T1, _T2>' and 'int'
99 | pend.pb(pp{int(ans.size()), data[i].second});
| ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from tea.cpp:1:
/usr/include/c++/9/bits/stl_pair.h:360:12: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(std::_PCC<((! std::is_same<int, _U1>::value) || (! std::is_same<int, _U2>::value)), int, int>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<((! std::is_same<int, _U1>::value) || (! std::is_same<int, _U2>::value)), int, int>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&)'
360 | constexpr pair(pair<_U1, _U2>&& __p)
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:360:12: note: template argument deduction/substitution failed:
tea.cpp:99:47: note: mismatched types 'std::pair<_T1, _T2>' and 'int'
99 | pend.pb(pp{int(ans.size()), data[i].second});
| ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from tea.cpp:1:
/usr/include/c++/9/bits/stl_pair.h:350:21: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(_MoveConstructiblePair<_U1, _U2>() && (! _ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&)'
350 | explicit constexpr pair(_U1&& __x, _U2&& __y)
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:350:21: note: template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_pair.h:341:12: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(_MoveConstructiblePair<_U1, _U2>() && _ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&)'
341 | constexpr pair(_U1&& __x, _U2&& __y)
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:341:12: note: template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_pair.h:332:17: note: candidate: 'template<class _U2, typename std::enable_if<_CopyMovePair<false, int, _U2>(), bool>::type <anonymous> > std::pair<_T1, _T2>::pair(const _T1&, _U2&&)'
332 | explicit pair(const _T1& __x, _U2&& __y)
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:332:17: note: template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_pair.h:325:18: note: candidate: 'template<class _U2, typename std::enable_if<_CopyMovePair<true, int, _U2>(), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(const _T1&, _U2&&)'
325 | constexpr pair(const _T1& __x, _U2&& __y)
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:325:18: note: template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_pair.h:318:27: note: candidate: 'template<class _U1, typename std::enable_if<_MoveCopyPair<false, _U1, int>(), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, const _T2&)'
318 | explicit constexpr pair(_U1&& __x, const _T2& __y)
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:318:27: note: template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_pair.h:311:18: note: candidate: 'template<class _U1, typename std::enable_if<_MoveCopyPair<true, _U1, int>(), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, const _T2&)'
311 | constexpr pair(_U1&& __x, const _T2& __y)
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:311:18: note: template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_pair.h:304:17: note: candidate: 'constexpr std::pair<_T1, _T2>::pair(std::pair<_T1, _T2>&&) [with _T1 = int; _T2 = int]'
304 | constexpr pair(pair&&) = default;
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:304:17: note: candidate expects 1 argument, 2 provided
/usr/include/c++/9/bits/stl_pair.h:303:17: note: candidate: 'constexpr std::pair<_T1, _T2>::pair(const std::pair<_T1, _T2>&) [with _T1 = int; _T2 = int]'
303 | constexpr pair(const pair&) = default;
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:303:17: note: candidate expects 1 argument, 2 provided
/usr/include/c++/9/bits/stl_pair.h:300:21: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(std::_PCC<((! std::is_same<int, _U1>::value) || (! std::is_same<int, _U2>::value)), int, int>::_ConstructiblePair<_U1, _U2>() && (! std::_PCC<((! std::is_same<int, _U1>::value) || (! std::is_same<int, _U2>::value)), int, int>::_ImplicitlyConvertiblePair<_U1, _U2>())), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(const std::pair<_U1, _U2>&)'
300 | explicit constexpr pair(const pair<_U1, _U2>& __p)
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:300:21: note: template argument deduction/substitution failed:
tea.cpp:99:47: note: mismatched types 'const std::pair<_T1, _T2>' and 'int'
99 | pend.pb(pp{int(ans.size()), data[i].second});
| ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from tea.cpp:1:
/usr/include/c++/9/bits/stl_pair.h:291:19: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(std::_PCC<((! std::is_same<int, _U1>::value) || (! std::is_same<int, _U2>::value)), int, int>::_ConstructiblePair<_U1, _U2>() && std::_PCC<((! std::is_same<int, _U1>::value) || (! std::is_same<int, _U2>::value)), int, int>::_ImplicitlyConvertiblePair<_U1, _U2>()), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(const std::pair<_U1, _U2>&)'
291 | constexpr pair(const pair<_U1, _U2>& __p)
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:291:19: note: template argument deduction/substitution failed:
tea.cpp:99:47: note: mismatched types 'const std::pair<_T1, _T2>' and 'int'
99 | pend.pb(pp{int(ans.size()), data[i].second});
| ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from tea.cpp:1:
/usr/include/c++/9/bits/stl_pair.h:269:26: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(_ConstructiblePair<_U1, _U2>() && (! _ImplicitlyConvertiblePair<_U1, _U2>())), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(const _T1&, const _T2&)'
269 | explicit constexpr pair(const _T1& __a, const _T2& __b)
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:269:26: note: template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_pair.h:260:17: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(_ConstructiblePair<_U1, _U2>() && _ImplicitlyConvertiblePair<_U1, _U2>()), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(const _T1&, const _T2&)'
260 | constexpr pair(const _T1& __a, const _T2& __b)
| ^~~~
/usr/include/c++/9/bits/stl_pair.h:260:17: note: