oj.uz

Submission #348335

# Submission time Handle Problem Language Result Execution time Memory
348335 2021-01-14T16:19:34 Z Mefarnis Hiring (IOI09_hiring) C++14
100 / 100
 378 ms 13192 KB 
#include <bits/stdc++.h>
#define maxn 500001
#define pb push_back
using namespace std;
typedef long long LL;

struct item {
	int c,q,id;
}ar[maxn];

bool comp(const item& a , const item& b) {
	return a.c*b.q < b.c*a.q;
}

bool operator<(const item& a , const item& b) {
	return a.q < b.q;
}

LL w;
int n;
double ansCost;
int ansIdx,ansCnt;

void solve(bool printSol) {
	LL currSum = 0;
	int currCnt = 0;
	priority_queue<item> heap;
	for( int i = 1 ; i <= n ; i++ ) {
		currCnt++;
		currSum += ar[i].q;
		heap.push(ar[i]);
		while(ar[i].c * currSum > w * ar[i].q) {
			item it = heap.top();
			heap.pop();
			currCnt--;
			currSum -= it.q;
		}
		if(printSol) {
			if(i == ansIdx) {
				vector<int> ans;
				while(!heap.empty()) {
					ans.pb(heap.top().id);
					heap.pop();
				}
				int sz = ans.size();
				sort(ans.begin(),ans.end());
				printf("%d\n",sz);
				for( int i = 0 ; i < sz ; i++ )
					printf("%d\n",ans[i]);
				break;
			}
		}
		else {
			double cost = (double) ar[i].c / ar[i].q * currSum;
			if(currCnt > ansCnt) {
				ansIdx = i;
				ansCnt = currCnt;
				ansCost = cost;
			}
			else if(currCnt == ansCnt && cost < ansCost) {
				ansIdx = i;
				ansCost = cost;
			}
		}
	}
}

int main() {
	scanf("%d%lld",&n,&w);
	for( int i = 1 ; i <= n ; i++ ) {
		ar[i].id = i;
		scanf("%d%d",&ar[i].c,&ar[i].q);
	}
	sort(ar+1,ar+n+1,comp);
	solve(false);
	if(ansIdx == 0)
		puts("0");
	else
		solve(true);
	return 0;
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  scanf("%d%lld",&n,&w);
      |  ~~~~~^~~~~~~~~~~~~~~~
hiring.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |   scanf("%d%d",&ar[i].c,&ar[i].q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 3 ms 364 KB Output is correct
10 Correct 3 ms 492 KB Output is correct
11 Correct 3 ms 364 KB Output is correct
12 Correct 5 ms 620 KB Output is correct
13 Correct 5 ms 492 KB Output is correct
14 Correct 8 ms 620 KB Output is correct
15 Correct 9 ms 724 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 12 ms 812 KB Output is correct
5 Correct 31 ms 1560 KB Output is correct
6 Correct 218 ms 7260 KB Output is correct
7 Correct 269 ms 10864 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3080 KB Output is correct
2 Correct 82 ms 3084 KB Output is correct
3 Correct 82 ms 3104 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 5540 KB Output is correct
2 Correct 125 ms 5544 KB Output is correct
3 Correct 123 ms 5540 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 11772 KB Output is correct
2 Correct 327 ms 11748 KB Output is correct
3 Correct 329 ms 11644 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 13192 KB Output is correct
2 Correct 376 ms 13096 KB Output is correct
3 Correct 377 ms 13096 KB Output is correct