oj.uz

답안 #733762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
733762 2023-05-01T09:21:17 Z penguin133 Hiring (IOI09_hiring) C++17
100 / 100
 630 ms 25916 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, w;
pii A[500005];

bool cmp(pii a, pii b){
	return ((long double)a.fi / (long double)a.se.fi) < ((long double)b.fi / (long double)b.se.fi);
}

struct node{
	int s, e, m, val, val2;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
		val = val2 = 0;
	}
	void upd(int p){
		if(s == e)val += s, val2++;
		else{
			if(p <= m)l->upd(p);
			else r->upd(p);
			val = l->val + r->val;
			val2 = l->val2 + r->val2;
		}
	}
	
	pi qry(int a, int b){
		if(s == a && e == b)return {val,val2};
		else if(b <= m)return l->qry(a, b);
		else if(a > m)return r->qry(a, b);
		else {
			pi lft = l->qry(a, m), rgt = r->qry(m+1, b);
			return {lft.fi + rgt.fi, lft.se + rgt.se};
		}
	}
}*root;


void solve(){
	cin >> n >> w;
	int mx = 0;
	for(int i=1;i<=n;i++)cin >> A[i].fi >> A[i].se.fi, A[i].se.se = i, mx = max(mx, A[i].se.fi);
	root = new node(1, mx);
	sort(A+1, A+n+1, cmp);
	vector <pi> v;
	pair<int, long double> ans2 = {0, 0.0L};
	vector <int> fin;
	int in = 0;
	for(int i=1;i<=n;i++){
		int x = w * A[i].se.fi / A[i].fi;
		x -= A[i].se.fi;
		if(x < 0){
			root->upd(A[i].se.fi);
			continue;
		}
		/*
		vector <int> tmp = {A[i].se.se};
		for(auto [j, k] : v){
			if(x >= j)x -= j, tmp.push_back(k);
		}
		v.push_back({A[i].se.fi, A[i].se.se});
		sort(v.begin(), v.end());
		int used = w * A[i].se.fi / A[i].fi - x;
		long double brub = (long double)(used * A[i].fi) / A[i].se.fi;
		if((int)tmp.size() > ans.fi || ((int)tmp.size() == ans.fi && ans.se < -brub))ans = {(int)tmp.size(), -brub}, fin = tmp;
		*/
		int lo = 1, hi = mx, ans = mx + 1, val = 0;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			pi res = root->qry(1, mid);
			if(res.fi >= x)ans = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		if(ans != 1)val = root->qry(1, ans - 1).se, x -= root->qry(1, ans - 1).fi;;
		if(ans != mx + 1){
			int left = root->qry(ans, ans).se;
			
			int mn = min(left, x / ans);
			val += min(x/ans, left);
			
			x -= mn * ans;
		}
		int used = w * A[i].se.fi / A[i].fi - x;
		long double brub = (long double)(used * A[i].fi) / A[i].se.fi;
		val++;
		if(val > ans2.fi || (val == ans2.fi && -brub > ans2.se))in = i;
		ans2 = max(ans2, {val, -brub});
		root->upd(A[i].se.fi);
	}
	/*
	cout << fin.size() << '\n';
	for(auto i : fin)cout << i << '\n';
	*/
	cout << ans2.fi << '\n';
	if(ans2.fi == 0)return;
	for(int i=1;i<in;i++){
		v.push_back(A[i].se);
	}
	sort(v.begin(), v.end());
	int x = w * A[in].se.fi / A[in].fi;
	x -= A[in].se.fi;
	fin.push_back(A[in].se.se);
	for(auto [j, k] : v){
		if(x >= j)x -= j, fin.push_back(k);
	}
	for(auto i : fin)cout << i << '\n';
	assert((int)fin.size() == ans2.fi);
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

hiring.cpp:122:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  122 | main(){
      | ^~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2004 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 5 ms 1620 KB Output is correct
9 Correct 8 ms 3028 KB Output is correct
10 Correct 8 ms 2388 KB Output is correct
11 Correct 11 ms 2992 KB Output is correct
12 Correct 8 ms 1360 KB Output is correct
13 Correct 15 ms 3052 KB Output is correct
14 Correct 20 ms 3412 KB Output is correct
15 Correct 22 ms 3444 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 28 ms 3540 KB Output is correct
5 Correct 52 ms 3212 KB Output is correct
6 Correct 378 ms 15548 KB Output is correct
7 Correct 479 ms 21432 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2840 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 4 ms 2772 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct

Subtask #6
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 8040 KB Output is correct
2 Correct 144 ms 7912 KB Output is correct
3 Correct 148 ms 7932 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 12240 KB Output is correct
2 Correct 244 ms 12276 KB Output is correct
3 Correct 239 ms 12284 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 567 ms 22944 KB Output is correct
2 Correct 550 ms 22976 KB Output is correct
3 Correct 551 ms 22952 KB Output is correct

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 630 ms 25916 KB Output is correct
2 Correct 612 ms 25848 KB Output is correct
3 Correct 627 ms 25908 KB Output is correct