oj.uz

Submission #432575

# Submission time Handle Problem Language Result Execution time Memory
432575 2021-06-18T11:18:38 Z rainboy Hiring (IOI09_hiring) C
100 / 100
 943 ms 15424 KB 
#include <stdio.h>
#include <string.h>

#define N	500000

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int ss[N], qq[N];

int compare(int i, int j) { return ss[i] * qq[j] - ss[j] * qq[i]; }

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int pq[N], iq[1 + N], cnt;

int lt(int i, int j) { return qq[i] > qq[j]; }

int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add(int i) {
	pq[i] = ++cnt, pq_up(i);
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];

	if (j != i)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

int main() {
	static int ii[N];
	int n, i, cnt_;
	long long w, p, p_, q_;

	scanf("%d%lld", &n, &w);
	for (i = 0; i < n; i++) {
		scanf("%d%d", &ss[i], &qq[i]);
		ii[i] = i;
	}
	sort(ii, 0, n);
	cnt_ = -1, p_ = q_ = -1, p = 0;
	for (i = 0; i < n; i++) {
		int i_ = ii[i], s = ss[i_], q = qq[i_];

		pq_add(i_), p += qq[i_];
		while (cnt && p * s > w * q)
			p -= qq[pq_remove_first()];
		if (cnt_ < cnt || cnt_ == cnt && p_ * q > p * s * q_)
			cnt_ = cnt, p_ = p * s, q_ = q;
	}
	memset(pq, 0, n * sizeof *pq), cnt = 0;
	p = 0;
	for (i = 0; i < n; i++) {
		int i_ = ii[i], s = ss[i_], q = qq[i_];

		pq_add(i_), p += qq[i_];
		while (cnt && p * s > w * q)
			p -= qq[pq_remove_first()];
		if (cnt_ == cnt && p_ * q == p * s * q_) {
			printf("%d\n", cnt);
			for (i = 1; i <= cnt; i++)
				printf("%d\n", iq[i] + 1);
			return 0;
		}
	}
	return 0;
}

Compilation message

hiring.c: In function 'main':
hiring.c:93:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   93 |   if (cnt_ < cnt || cnt_ == cnt && p_ * q > p * s * q_)
      |                     ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
hiring.c:80:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d%lld", &n, &w);
      |  ^~~~~~~~~~~~~~~~~~~~~~~
hiring.c:82:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d%d", &ss[i], &qq[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 7 ms 548 KB Output is correct
13 Correct 12 ms 460 KB Output is correct
14 Correct 10 ms 588 KB Output is correct
15 Correct 10 ms 628 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 16 ms 892 KB Output is correct
5 Correct 30 ms 1976 KB Output is correct
6 Correct 442 ms 9188 KB Output is correct
7 Correct 543 ms 12132 KB Output is correct

Subtask #3
6.0 / 6.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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 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 1 ms 348 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 3556 KB Output is correct
2 Correct 115 ms 3616 KB Output is correct
3 Correct 114 ms 3612 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 6088 KB Output is correct
2 Correct 166 ms 6056 KB Output is correct
3 Correct 168 ms 6044 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 13832 KB Output is correct
2 Correct 636 ms 13836 KB Output is correct
3 Correct 783 ms 13784 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 15424 KB Output is correct
2 Correct 872 ms 15412 KB Output is correct
3 Correct 943 ms 15424 KB Output is correct