Submission #1089892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089892		peacebringer1667	Hiring (IOI09_hiring)	C++17	100 / 100	305 ms	34960 KiB

hiring

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
#define pirp pair<int,ldb>
using namespace std;
const int maxn = 5e5 + 5;
const int MN = 2e4 + 5;

struct DSA{
	int num = 0;ldb cost = 0;
	bool operator <(const DSA&other) const{
		return (num < other.num) || (num == other.num && cost > other.cost);
	}
	bool operator >(const DSA&other) const{
		return (num > other.num) || (num == other.num && cost < other.cost);
	}
};

struct CTDL{
	int S = 0,Q = 0;ldb cpr = 0;int id = 0;
	bool operator <(const CTDL&other) const{
		return (cpr < other.cpr);
	}
};

struct segment_tree{
	ll seg[4*MN];int cnt[4*maxn];
	
	DSA calc(int l,int r,int v,ldb cap){
		if (l == r){
			ldb x = l;
			//x * y <= cap, y <= cnt[v]
			ll y = min((ldb)cap/(ldb)x,(ldb)cnt[v]);
			
			return {(int)y,x * y};
		}
		
		int w = (l + r)/2;
		if (seg[2*v + 1] >= cap)
		  return calc(l,w,2*v + 1,cap);
		
		DSA res = {cnt[2*v + 1],(ldb)seg[2*v + 1]};
		cap -= seg[2*v + 1];
		
		DSA tmp = calc(w + 1,r,2*v + 2,cap);
		res.num += tmp.num;
		res.cost += tmp.cost;
		
		return res;
	}
	
	void update(int l,int r,int v,int p,int val){
		if (l > p || r < p) return;
		if (l == r){
			cnt[v] += val;
			seg[v] = (ll)p * (ll)cnt[v];
			return;
		}
		
		int w = (l + r)/2;
		update(l,w,2*v + 1,p,val);
		update(w + 1,r,2*v + 2,p,val);
		seg[v] = seg[2*v + 1] + seg[2*v + 2];
		cnt[v] = cnt[2*v + 1] + cnt[2*v + 2];
	}
		
} seg;

CTDL a[maxn];

void input(int n){
	for (int i = 1 ; i <= n ; i++){
		cin >> a[i].S >> a[i].Q;
		a[i].cpr = (ldb)a[i].S/a[i].Q;
		a[i].id = i;
	}
	sort(a + 1,a + 1 + n);
}

vector <int> lst;
void TRACE(DSA res,int trace){
	vector <pir> vec;
	lst.push_back(a[trace].id);
	for (int i = 1 ; i < trace ; i++)
	   vec.push_back({a[i].Q,a[i].id});
	   
	sort(vec.begin(),vec.end());
	for (int i = 0 ; i < res.num - 1 ; i++)
	  lst.push_back(vec[i].se);
	
	sort(lst.begin(),lst.end());
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n;ll W;
	cin >> n >> W;
	input(n);
	DSA res = {0,(ldb)W};
	int N = 0;
	for (int i = 1 ; i <= n ; i++) N = max(N,a[i].Q);
	
	int trace = 0;
	for (int i = 1 ; i <= n ; i++) if (a[i].S <= W){
		ldb cap = (ldb)(W - a[i].S)/(ldb)a[i].cpr;
		DSA T = seg.calc(1,N,0,cap);
		
		T.cost *= (ldb)a[i].cpr;
		T.cost += (ldb)a[i].S;
		T.num++;
		
		if (res < T){
			res = T;
			trace = i;
		}
		seg.update(1,N,0,a[i].Q,1);
	}
	else
	seg.update(1,N,0,a[i].Q,1);
	
	TRACE(res,trace);
	
	cout << lst.size() << "\n";
	for (int x : lst) cout << x << "\n";

	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 28 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6