oj.uz

Submission #899802

# Submission time Handle Problem Language Result Execution time Memory
899802 2024-01-07T03:02:48 Z josanneo22 Hiring (IOI09_hiring) C++17
0 / 100
 151 ms 14164 KB 
#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, 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() {
	memset(cnt,0,sizeof(cnt));
	memset(buc,0,sizeof(buc));
	scanf("%d%d", &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 = 0, old_fraction_bottom = 0;
	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 new_cnt = res.second;
		i64 cur_fraction_top = A[i].salary * sum;
		i64 cur_fraction_bottom = A[i].qualifications;
		if (new_cnt > best || (new_cnt == best && cur_fraction_top * old_fraction_bottom < old_fraction_top * cur_fraction_bottom)) {
			best = new_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;
	});
	printf("%d", best);
	L(i, 0, best - 1) printf("%d\n", A[starting_position + i].id);
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d%d", &N, &W);
      |  ~~~~~^~~~~~~~~~~~~~~~
hiring.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d%d", &A[i].salary, &A[i].qualifications);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 KB Output isn't correct
2 Incorrect 2 ms 6492 KB Output isn't correct
3 Incorrect 2 ms 6592 KB Output isn't correct
4 Incorrect 2 ms 6492 KB Output isn't correct
5 Incorrect 2 ms 6644 KB Output isn't correct
6 Incorrect 3 ms 6492 KB Output isn't correct
7 Incorrect 3 ms 6492 KB Output isn't correct
8 Incorrect 3 ms 6492 KB Output isn't correct
9 Incorrect 3 ms 6492 KB Output isn't correct
10 Incorrect 3 ms 6492 KB Output isn't correct
11 Incorrect 4 ms 6492 KB Output isn't correct
12 Incorrect 4 ms 6492 KB Output isn't correct
13 Incorrect 5 ms 6488 KB Output isn't correct
14 Incorrect 5 ms 6492 KB Output isn't correct
15 Incorrect 6 ms 6744 KB Output isn't correct

Subtask #2
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 KB Output isn't correct
2 Incorrect 3 ms 6492 KB Output isn't correct
3 Incorrect 2 ms 6648 KB Output isn't correct
4 Incorrect 7 ms 6596 KB Output isn't correct
5 Incorrect 20 ms 10844 KB Output isn't correct
6 Incorrect 94 ms 12988 KB Expected int32, but "5014164672" found
7 Incorrect 111 ms 12880 KB Output isn't correct

Subtask #3
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 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 6492 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 6492 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 36 ms 10852 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 57 ms 10848 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 136 ms 13540 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 151 ms 14164 KB Expected int32, but "6950395472" found
2 Halted 0 ms 0 KB -