oj.uz

답안 #588972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
588972 2022-07-04T08:21:35 Z Drew_ Hiring (IOI09_hiring) C++17
100 / 100
 359 ms 29756 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define f1 first
#define s2 second
// #define int long long

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using pl = pair<ll, ll>;

const int MAX = 5e5 + 69;

struct Segtree
{
	int n;
	pair<ll, int> st[1 << 20];
	Segtree() {}
	Segtree(int n_) : n(n_) { memset(st, 0, sizeof(st)); }

	inline void add(int p, ll val)
	{
		const auto add_ = [&](const auto &self, int node, int l, int r) -> void
		{
			if (l > p || r < p)
				return;
			if (p <= l && r <= p)
			{
				st[node].f1 += val; st[node].s2++;
				return;
			}
			int mid = (l + r) >> 1;
			self(self, node << 1, l, mid);
			self(self, node << 1 | 1, mid+1, r);

			st[node].f1 = st[node << 1].f1 + st[node << 1 | 1].f1;
			st[node].s2 = st[node << 1].s2 + st[node << 1 | 1].s2;
		};
		add_(add_, 1, 1, n);
	}

	inline pair<int, ld> query(ll val, int S)
	{
		int res = 0;
		const auto query_ = [&](const auto &self, int node, int l, int r) -> void
		{
			if (st[node].f1 * S <= val)
			{
				res += st[node].s2;
				val -= st[node].f1 * S;
				return;
			}

			if (l == r)
				return;
			
			int mid = (l + r) >> 1;
			if (st[node << 1].f1 * S <= val)
			{
				res += st[node << 1].s2;
				val -= st[node << 1].f1 * S;
				self(self, node << 1 | 1, mid+1, r);
			}
			else self(self, node << 1, l, mid);
		};
		query_(query_, 1, 1, n);
		return { res, val };
	}
};

int32_t main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;
	ll W;
	cin >> N >> W;

	vector<array<int, 4>> V(N);
	for (auto &[s, q, i, idx] : V)
		cin >> s >> q;
	for (int i = 0; i < N; ++i)
		V[i][3] = i+1;

	sort(V.begin(), V.end(), [](auto &x, auto &y){
		return x[1] < y[1];
	});

	for (int i = 0; i < N; ++i)
		V[i][2] = i+1;

	sort(V.begin(), V.end(), [](auto &x, auto &y){
		return 1ll * x[0] * y[1] < 1ll * y[0] * x[1];
	});

	Segtree st(N);

	pair<int, ld> res = {0, 0};
	int id = -1;
	for (int j = 0; j < N; ++j)
	{
		auto &[s, q, i, idx] = V[j];

		st.add(i, q);
		pair<int, ld> cur = st.query(1ll * W * q, s);
		cur.s2 /= q;

		if (cur > res)
			res = cur, id = j;
	}

	sort(V.begin(), V.begin()+id+1, [](auto &x, auto &y){
		return x[1] < y[1];
	});

	cout << res.f1 << '\n';
	for (int i = 0; i < res.f1; ++i)
		cout << V[i][3] << '\n';
	return 0;
}

Compilation message

hiring.cpp: In constructor 'Segtree::Segtree(int)':
hiring.cpp:21:52: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   21 |  Segtree(int n_) : n(n_) { memset(st, 0, sizeof(st)); }
      |                                                    ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from hiring.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, int>' declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 16724 KB Output is correct
2 Correct 11 ms 16716 KB Output is correct
3 Correct 11 ms 16724 KB Output is correct
4 Correct 9 ms 16728 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16748 KB Output is correct
7 Correct 12 ms 16748 KB Output is correct
8 Correct 11 ms 16724 KB Output is correct
9 Correct 11 ms 16852 KB Output is correct
10 Correct 11 ms 16868 KB Output is correct
11 Correct 13 ms 16872 KB Output is correct
12 Correct 12 ms 16852 KB Output is correct
13 Correct 14 ms 16924 KB Output is correct
14 Correct 16 ms 17072 KB Output is correct
15 Correct 18 ms 17236 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16732 KB Output is correct
2 Correct 10 ms 16736 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 19 ms 17260 KB Output is correct
5 Correct 40 ms 18356 KB Output is correct
6 Correct 214 ms 25248 KB Output is correct
7 Correct 281 ms 27744 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16696 KB Output is correct
2 Correct 10 ms 16744 KB Output is correct
3 Correct 10 ms 16736 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 16724 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 9 ms 16632 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16724 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 10 ms 16744 KB Output is correct

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 19840 KB Output is correct
2 Correct 95 ms 19844 KB Output is correct
3 Correct 78 ms 19836 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 22264 KB Output is correct
2 Correct 125 ms 22276 KB Output is correct
3 Correct 129 ms 22348 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 28620 KB Output is correct
2 Correct 290 ms 28620 KB Output is correct
3 Correct 316 ms 28568 KB Output is correct

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 349 ms 29612 KB Output is correct
2 Correct 339 ms 29632 KB Output is correct
3 Correct 359 ms 29756 KB Output is correct