Submission #396640

#	Time	Username	Problem	Language	Result	Execution time	Memory
396640		peuch	Hiring (IOI09_hiring)	C++17	100 / 100	950 ms	42336 KiB

hiring

#include<bits/stdc++.h>
using namespace std;
 
const int MAXN = 5e5 + 10;
const int MAXQ = 2e4 + 10;
 
int n;
double w;
double s[MAXN], q[MAXN];
vector<int> ord;
 
bool cmp(int a, int b){
	return s[a] * q[b] < s[b] * q[a];
}
 
int main(){
	scanf("%d %lf", &n, &w);
	for(int i = 1; i <= n; i++){
		scanf("%lf %lf", &s[i], &q[i]);
		ord.push_back(i);
	}	
	sort(ord.begin(), ord.end(), cmp);
	int ans = 0, id = 0;
	double cost = 0;
	multiset<double> aux;
	double sum = 0;
	for(int i = 0; i < ord.size(); i++){
		int cur = ord[i];
		sum += q[cur];
		aux.insert(q[cur]);
		while(!aux.empty() && sum * s[cur] > w * q[cur]){
			multiset<double>::iterator it;
			it = aux.end();
			it--;
			sum -= *it;
			aux.erase(it);
		}
		if(aux.size() > ans) ans = aux.size(), cost = sum * s[cur] / q[cur], id = i;
		if(aux.size() == ans && cost > sum * s[cur] / q[cur]) cost = sum * s[cur] / q[cur], id = i;
	}
	printf("%d\n", ans);
	set<pair<double, int> > aux2;
	for(int i = 0; i <= id; i++)
		aux2.insert(make_pair(q[ord[i]], ord[i]));
	while(ans--){
		printf("%d\n", aux2.begin()->second);
		aux2.erase(aux2.begin());
	}
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i = 0; i < ord.size(); i++){
      |                 ~~^~~~~~~~~~~~
hiring.cpp:38:17: warning: comparison of integer expressions of different signedness: 'std::multiset<double>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |   if(aux.size() > ans) ans = aux.size(), cost = sum * s[cur] / q[cur], id = i;
      |      ~~~~~~~~~~~^~~~~
hiring.cpp:39:17: warning: comparison of integer expressions of different signedness: 'std::multiset<double>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |   if(aux.size() == ans && cost > sum * s[cur] / q[cur]) cost = sum * s[cur] / q[cur], id = i;
      |      ~~~~~~~~~~~^~~~~~
hiring.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  scanf("%d %lf", &n, &w);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
hiring.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |   scanf("%lf %lf", &s[i], &q[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 28 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6