# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
436837 | adamjinwei | Hiring (IOI09_hiring) | C++14 | 845 ms | 39748 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
#define inf 1000000000000000007ULL
#define mod 1000000007
#define rnd() dist(rand_num)
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
//#define int long long
using namespace std;
unsigned seed=std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(seed);
uniform_int_distribution<int> dist(0,inf);
template <typename T> void read(T &x){
x=0;char ch=getchar();int fh=1;
while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
x*=fh;
}
template <typename T> void write(T x) {
if (x<0) x=-x,putchar('-');
if (x>9) write(x/10);
putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
int n;
long long w;
pair<pair<long double,int>,int> p[500005];
signed main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
read(n);read(w);
for(register int i=1;i<=n;++i)
{
int s,q;
read(s);read(q);
p[i]=make_pair(make_pair((long double)s/(long double)q,q),i);
}
sort(p+1,p+n+1);
int ans=0;
long double mn=inf;
__gnu_pbds::priority_queue<pair<int,int>,less<pair<int,int>>,pairing_heap_tag> pq;
unsigned long long sum=0;
for(register int i=1;i<=n;++i)
{
pq.push(make_pair(p[i].first.second,i));
sum+=p[i].first.second;
while(sum*p[i].first.first>w+1e-8)
{
sum-=pq.top().first;
pq.pop();
}
if(ans<pq.size())
{
ans=pq.size();
mn=sum*p[i].first.first;
}
else if(ans==pq.size()&&sum*p[i].first.first<mn-1e-8)
{
mn=sum*p[i].first.first;
}
}
sum=0;
while(!pq.empty()) pq.pop();
for(register int i=1;i<=n;++i)
{
pq.push(make_pair(p[i].first.second,i));
sum+=p[i].first.second;
while(sum*p[i].first.first>w+1e-8)
{
sum-=pq.top().first;
pq.pop();
}
if(ans==pq.size()&&fabs(sum*p[i].first.first-mn)<1e-8)
{
writeln(ans);
while(!pq.empty())
{
writeln(p[pq.top().second].second);
pq.pop();
}
return 0;
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |