Submission #396627

#	Time	Username	Problem	Language	Result	Execution time	Memory
396627		peuch	Hiring (IOI09_hiring)	C++17	30 / 100	857 ms	37820 KiB

hiring

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 10;
const int MAXQ = 2e4 + 10;

int n;
double w;
double s[MAXN], q[MAXN];
vector<int> ord;

double seg[4 * MAXQ];
int cnt[4 * MAXQ];

void update(int pos, int ini, int fim, double id);
pair<int, double> bb(int pos, int ini, int fim, double val);

bool cmp(int a, int b){
	return s[a] * q[b] < s[b] * q[a];
}

int main(){
	scanf("%d %lf", &n, &w);
	for(int i = 1; i <= n; i++){
		scanf("%lf %lf", &s[i], &q[i]);
		ord.push_back(i);
	}	
	sort(ord.begin(), ord.end(), cmp);
	int ans = 0, id = 0;
	double qnt = 0;
	for(int i = 0; i < ord.size(); i++){
		int cur = ord[i];
		update(1, 1, MAXQ, q[cur]);
		pair<int, double> val = bb(1, 1, MAXQ, w * q[cur] / s[cur]); 
		val.second *= s[cur]/q[cur];
		if(val.first > ans) ans = val.first, qnt = val.second, id = i;
		if(val.first < ans) continue;
		if(qnt > val.second) ans = val.first, qnt = val.second, id = i;
	}
	printf("%d\n", ans);
	set<pair<double, int> > aux;
	for(int i = 0; i <= id; i++)
		aux.insert(make_pair(q[ord[i]], i + 1));
	while(ans--){
		printf("%d\n", ans + 1);
	}
}

void update(int pos, int ini, int fim, double id){
	if(ini > id || fim < id) return;
	if(ini == fim){
		seg[pos] += id;
		cnt[pos]++;
		return;
	} 
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	update(e, ini, mid, id);
	update(d, mid + 1, fim, id);
	seg[pos] = seg[e] + seg[d];
	cnt[pos] = cnt[e] + cnt[d];
}

pair<int, double> bb(int pos, int ini, int fim, double val){
	pair<int, double> ret = make_pair(0, 0);
	if(ini == fim) return ret;
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;	
	if(seg[e] > val)
		return bb(e, ini, mid, val);
	ret = bb(d, mid + 1, fim, val - seg[e]);
	ret.first += cnt[e];
	ret.second += seg[e];
	return ret;
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < ord.size(); i++){
      |                 ~~^~~~~~~~~~~~
hiring.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |  scanf("%d %lf", &n, &w);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
hiring.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |   scanf("%lf %lf", &s[i], &q[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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