oj.uz

Submission #436837

# Submission time Handle Problem Language Result Execution time Memory
436837 2021-06-25T03:23:12 Z adamjinwei Hiring (IOI09_hiring) C++14
100 / 100
 845 ms 39748 KB 
#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;
}

Compilation message

hiring.cpp:4:13: warning: overflow in conversion from 'long long unsigned int' to 'int' changes value from '1000000000000000007' to '-1486618617' [-Woverflow]
    4 | #define inf 1000000000000000007ULL
      |             ^~~~~~~~~~~~~~~~~~~~~~
hiring.cpp:13:38: note: in expansion of macro 'inf'
   13 | uniform_int_distribution<int> dist(0,inf);
      |                                      ^~~
hiring.cpp: In function 'int main()':
hiring.cpp:57:9: warning: comparison of integer expressions of different signedness: 'int' and '__gnu_pbds::detail::left_child_next_sibling_heap<std::pair<int, int>, std::less<std::pair<int, int> >, __gnu_pbds::null_type, std::allocator<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   if(ans<pq.size())
      |      ~~~^~~~~~~~~~
hiring.cpp:62:14: warning: comparison of integer expressions of different signedness: 'int' and '__gnu_pbds::detail::left_child_next_sibling_heap<std::pair<int, int>, std::less<std::pair<int, int> >, __gnu_pbds::null_type, std::allocator<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   else if(ans==pq.size()&&sum*p[i].first.first<mn-1e-8)
      |           ~~~^~~~~~~~~~~
hiring.cpp:78:9: warning: comparison of integer expressions of different signedness: 'int' and '__gnu_pbds::detail::left_child_next_sibling_heap<std::pair<int, int>, std::less<std::pair<int, int> >, __gnu_pbds::null_type, std::allocator<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   if(ans==pq.size()&&fabs(sum*p[i].first.first-mn)<1e-8)
      |      ~~~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 4 ms 588 KB Output is correct
10 Correct 5 ms 588 KB Output is correct
11 Correct 4 ms 588 KB Output is correct
12 Correct 6 ms 844 KB Output is correct
13 Correct 4 ms 716 KB Output is correct
14 Correct 9 ms 1100 KB Output is correct
15 Correct 11 ms 1228 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 15 ms 1616 KB Output is correct
5 Correct 28 ms 3944 KB Output is correct
6 Correct 376 ms 19656 KB Output is correct
7 Correct 372 ms 27192 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 7660 KB Output is correct
2 Correct 181 ms 8900 KB Output is correct
3 Correct 124 ms 8844 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 13380 KB Output is correct
2 Correct 131 ms 15412 KB Output is correct
3 Correct 116 ms 15368 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 29908 KB Output is correct
2 Correct 577 ms 34764 KB Output is correct
3 Correct 588 ms 34816 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 34436 KB Output is correct
2 Correct 771 ms 39748 KB Output is correct
3 Correct 845 ms 39716 KB Output is correct