oj.uz

Submission #899813

# Submission time Handle Problem Language Result Execution time Memory
899813 2024-01-07T04:42:33 Z josanneo22 Hiring (IOI09_hiring) C++17
2 / 100
 213 ms 18516 KB 
#pragma warning(suppress : 4996)
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

#define L(i,j,k) for(int i=j;i<=k;i++)
#define R(i,j,k) for(int i=j;i>=k;i--)

constexpr int _N = 5E5 + 500;

struct worker {
	int salary, qualifications, id;
	bool operator < (worker& b) {
		return salary * b.qualifications > b.salary * b.qualifications;
	}
}A[_N];													   
int cnt[_N], N; i64 W, buc[_N];
i64 T[_N];
void add(int x,int v) {
	while (x <= N) {
		T[x] += v;
		cnt[x]++;
		x += x & -x;
	}
}
pair<i64, int> query(i64 limit) {
	i64 sum = 0, total = 0, ind = 0;
	R(i, 18, 0) {
		int new_ind = ind + (1 << i);
		if (new_ind > N) continue;
		if (sum + T[new_ind] > limit) continue;
		ind = new_ind;
		sum += T[ind]; total += cnt[ind];
	}
	return make_pair(sum, total);
}
int main() {
	scanf("%d%lld", &N, &W);
	L(i, 1, N) {
		scanf("%d%d", &A[i].salary, &A[i].qualifications);
		buc[A[i].qualifications]++;
		A[i].id = i;
	}
	sort(A + 1, A + 1 + N);
	L(i, 1, _N - 1) buc[i] += buc[i - 1];
	int starting_position = 0, best = -1;
	i64 old_fraction_top, old_fraction_bottom;
	R(i, N, 1) {
		int p = buc[A[i].qualifications]--;
		add(p, A[i].qualifications);
		auto res = query(W * A[i].qualifications / A[i].salary);
		i64 sum = res.first; int cnt = res.second;
		i64 cur_fraction_top = A[i].salary * sum;
		i64 cur_fraction_bottom = A[i].qualifications;
		if (cnt > best || (cnt == best && cur_fraction_top * old_fraction_bottom < old_fraction_bottom * cur_fraction_bottom)) {
			best = cnt;
			starting_position = i;
			old_fraction_bottom = cur_fraction_bottom;
			old_fraction_top = cur_fraction_top;
		}
	}
	sort(A + starting_position, A + N + 1, [&](auto& a, auto& b) {
		return a.qualifications < b.qualifications;
	});
	cout << best << '\n';
	L(i, 0, best - 1)	cout << A[starting_position + i].id << '\n';

}

Compilation message

hiring.cpp:1: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    1 | #pragma warning(suppress : 4996)
      | 
hiring.cpp: In function 'int main()':
hiring.cpp:47:6: warning: variable 'old_fraction_top' set but not used [-Wunused-but-set-variable]
   47 |  i64 old_fraction_top, old_fraction_bottom;
      |      ^~~~~~~~~~~~~~~~
hiring.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%lld", &N, &W);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
hiring.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d%d", &A[i].salary, &A[i].qualifications);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hiring.cpp:55:98: warning: 'old_fraction_bottom' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |   if (cnt > best || (cnt == best && cur_fraction_top * old_fraction_bottom < old_fraction_bottom * cur_fraction_bottom)) {
      |                                                                              ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Incorrect 2 ms 8540 KB Output isn't correct
3 Incorrect 3 ms 8540 KB Output isn't correct
4 Incorrect 2 ms 8540 KB Output isn't correct
5 Incorrect 2 ms 8540 KB Output isn't correct
6 Incorrect 3 ms 8540 KB Output isn't correct
7 Incorrect 3 ms 8540 KB Output isn't correct
8 Incorrect 3 ms 8540 KB Output isn't correct
9 Incorrect 4 ms 8540 KB Output isn't correct
10 Incorrect 4 ms 8540 KB Output isn't correct
11 Incorrect 4 ms 8540 KB Output isn't correct
12 Incorrect 4 ms 8540 KB Output isn't correct
13 Incorrect 6 ms 8540 KB Output isn't correct
14 Incorrect 6 ms 8644 KB Output isn't correct
15 Incorrect 7 ms 8644 KB Output isn't correct

Subtask #2
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8540 KB Output isn't correct
2 Incorrect 3 ms 8540 KB Output isn't correct
3 Incorrect 2 ms 8652 KB Output isn't correct
4 Incorrect 10 ms 8796 KB Output isn't correct
5 Incorrect 21 ms 12984 KB Output isn't correct
6 Incorrect 129 ms 15976 KB Output isn't correct
7 Incorrect 187 ms 17000 KB Output isn't correct

Subtask #3
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 13244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 13416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 184 ms 17236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 18516 KB Output isn't correct
2 Halted 0 ms 0 KB -