| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 287376 | Namnamseo | Hiring (IOI09_hiring) | 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;
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define pb push_back
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }
int n;
struct bunsoo{
ll mo,ja;
bunsoo(){ mo=1; ja=0; }
bunsoo(ll a,ll b){ mo=a; ja=b; }
bool operator<(const bunsoo& other) const {
return ja*other.mo < mo*other.ja;
}
};
struct segtree {
static const int M=524288;
ll tree[M*2];
void upd(int a,ll b){
a += M;
while(a) tree[a]+=b, a>>=1;
}
ll rangesum(int a,int b){
ll ret=0;
a+=M; b+=M;
while(a<=b){
if(a%2==1) ret+=tree[a++];
if(b%2==0) ret+=tree[b--];
a/=2; b/=2;
}
return ret;
}
int findpos(ll lim){
int pos=1;
ll sl = 0;
while(pos<M){
pos *= 2;
if(sl + tree[pos] <= lim){
sl += tree[pos];
++pos;
}
}
pos=1;
ll cur=0;
while(pos<M){
pos *= 2;
if(cur + tree[pos] < sl){
cur += tree[pos];
++pos;
}
}
return pos-M;
}
} segT, cntT;
struct saram {
bunsoo gij;
int s,q;
int ind;
} data[500010];
ll w;
vector<int> qs;
set<pp> qset;
int main(){
read(n,w);
for(int i=1; i<=n; ++i){
int s,q; read(s,q);
qs.pb(q);
data[i]={bunsoo(s,q), s, q, i};
}
sort(all(qs));
for(int i=0; i<n; ++i)
qset.insert({qs[i],i});
sort(data+1, data+n+1,
[](const saram& a, const saram& b){
return a.gij < b.gij;
});
int ans = -1;
int ans_ind = -1;
bunsoo ans_cost(1, 2e9);
for(int i=n; 1<=i; --i){
auto it = qset.lower_bound({data[i].q,0});
int qi = it->second;
qset.erase(it);
// printf("Updating: %d\n", qi);
segT.upd(qi, data[i].q);
cntT.upd(qi, 1);
ll up_lim = w*data[i].q / data[i].s;
// printf("limit %lld\n", up_lim);
int t = segT.findpos(up_lim);
// printf("t %d\n", t);
int cnt = cntT.rangesum(0, t);
ll qs = segT.rangesum(0, t);
// printf("cnt %d; qs %lld\n", cnt, qs);
// putchar(10);
bunsoo tmp(data[i].q, qs*data[i].s);
if(ans < cnt){
ans = cnt;
ans_cost = tmp;
ans_ind = i;
} else if(ans == cnt){
if(tmp < ans_cost){
ans_cost = tmp;
ans_ind = i;
}
}
}
printf("%d\n", ans);
sort(data+ans_ind, data+n+1, [](const saram& a, const saram& b){
return a.q < b.q;
});
for(int i=ans_ind; i<ans_ind + ans; ++i){
printf("%d\n", data[i].ind);
}
return 0;
}
Compilation message (stderr)
hiring.cpp: In function 'int main()':
hiring.cpp:80:3: error: reference to 'data' is ambiguous
80 | data[i]={bunsoo(s,q), s, q, 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 hiring.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()))
| ^~~~
hiring.cpp:68:3: note: 'saram data [500010]'
68 | } data[500010];
| ^~~~
hiring.cpp:86:7: error: reference to 'data' is ambiguous
86 | sort(data+1, data+n+1,
| ^~~~
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 hiring.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()))
| ^~~~
hiring.cpp:68:3: note: 'saram data [500010]'
68 | } data[500010];
| ^~~~
hiring.cpp:86:15: error: reference to 'data' is ambiguous
86 | sort(data+1, data+n+1,
| ^~~~
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 hiring.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()))
| ^~~~
hiring.cpp:68:3: note: 'saram data [500010]'
68 | } data[500010];
| ^~~~
hiring.cpp:96:31: error: reference to 'data' is ambiguous
96 | auto it = qset.lower_bound({data[i].q,0});
| ^~~~
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 hiring.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()))
| ^~~~
hiring.cpp:68:3: note: 'saram data [500010]'
68 | } data[500010];
| ^~~~
hiring.cpp:96:43: error: no matching function for call to 'std::set<std::pair<int, int> >::lower_bound(<brace-enclosed initializer list>)'
96 | auto it = qset.lower_bound({data[i].q,0});
| ^
In file included from /usr/include/c++/9/set:61,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:87,
from hiring.cpp:1:
/usr/include/c++/9/bits/stl_set.h:829:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree_const_iterator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<int, int>]'
829 | lower_bound(const key_type& __x)
| ^~~~~~~~~~~
/usr/include/c++/9/bits/stl_set.h:829:35: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<int, int>&'}
829 | lower_bound(const key_type& __x)
| ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_set.h:833:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::const_iterator std::set<_Key, _Compare, _Alloc>::lower_bound(const key_type&) const [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree_const_iterator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<int, int>]'
833 | lower_bound(const key_type& __x) const
| ^~~~~~~~~~~
/usr/include/c++/9/bits/stl_set.h:833:35: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<int, int>&'}
833 | lower_bound(const key_type& __x) const
| ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_set.h:839:2: note: candidate: 'template<class _Kt> decltype ((std::set<_Key, _Compare, _Alloc>::iterator)(((std::set<_Key, _Compare, _Alloc>*)this)->std::set<_Key, _Compare, _Alloc>::_M_t._M_lower_bound_tr(__x))) std::set<_Key, _Compare, _Alloc>::lower_bound(const _Kt&) [with _Kt = _Kt; _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
839 | lower_bound(const _Kt& __x)
| ^~~~~~~~~~~
/usr/include/c++/9/bits/stl_set.h:839:2: note: template argument deduction/substitution failed:
hiring.cpp:96:43: note: couldn't deduce template parameter '_Kt'
96 | auto it = qset.lower_bound({data[i].q,0});
| ^
In file included from /usr/include/c++/9/set:61,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:87,
from hiring.cpp:1:
/usr/include/c++/9/bits/stl_set.h:845:2: note: candidate: 'template<class _Kt> decltype ((std::set<_Key, _Compare, _Alloc>::const_iterator)(((const std::set<_Key, _Compare, _Alloc>*)this)->std::set<_Key, _Compare, _Alloc>::_M_t._M_lower_bound_tr(__x))) std::set<_Key, _Compare, _Alloc>::lower_bound(const _Kt&) const [with _Kt = _Kt; _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
845 | lower_bound(const _Kt& __x) const
| ^~~~~~~~~~~
/usr/include/c++/9/bits/stl_set.h:845:2: note: template argument deduction/substitution failed:
hiring.cpp:96:43: note: couldn't deduce template parameter '_Kt'
96 | auto it = qset.lower_bound({data[i].q,0});
| ^
hiring.cpp:101:16: error: reference to 'data' is ambiguous
101 | segT.upd(qi, data[i].q);
| ^~~~
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 hiring.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()))
| ^~~~
hiring.cpp:68:3: note: 'saram data [500010]'
68 | } data[500010];
| ^~~~
hiring.cpp:104:17: error: reference to 'data' is ambiguous
104 | ll up_lim = w*data[i].q / data[i].s;
| ^~~~
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 hiring.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()))
| ^~~~
hiring.cpp:68:3: note: 'saram data [500010]'
68 | } data[500010];
| ^~~~
hiring.cpp:104:29: error: reference to 'data' is ambiguous
104 | ll up_lim = w*data[i].q / data[i].s;
| ^~~~
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 hiring.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()))
| ^~~~
hiring.cpp:68:3: note: 'saram data [500010]'
68 | } data[500010];
| ^~~~
hiring.cpp:115:14: error: reference to 'data' is ambiguous
115 | bunsoo tmp(data[i].q, qs*data[i].s);
| ^~~~
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 hiring.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()))
| ^~~~
hiring.cpp:68:3: note: 'saram data [500010]'
68 | } data[500010];
| ^~~~
hiring.cpp:115:28: error: reference to 'data' is ambiguous
115 | bunsoo tmp(data[i].q, qs*data[i].s);
| ^~~~
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 hiring.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