Submission #396628

#	Time	Username	Problem	Language	Result	Execution time	Memory
396628		peuch	Hiring (IOI09_hiring)	C++17	52 / 100	1022 ms	37732 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);
void query(int pos, int ini, int fim, int p, int q);
int 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]);
		int k = bb(1, 1, MAXQ, w * q[cur] / s[cur]); 
		
		query(1, 1, MAXQ, 1, k - 1);
		int valC = cnt[0];
		int valW = seg[0] * s[cur] / q[cur];
		
		if(valC < ans) continue;
		if(valC > ans) ans = valC, qnt = valW, id = i;
		if(qnt > valW) ans = valC, qnt = valW, 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]], ord[i]));
	while(ans--){
		printf("%d\n", aux.begin()->second);
		aux.erase(aux.begin());
	}
}
 
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];
}
 
int bb(int pos, int ini, int fim, double val){
	pair<int, double> ret = make_pair(0, 0);
	if(ini == fim) return ini;
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;	
	if(seg[e] > val)
		return bb(e, ini, mid, val);
	return bb(d, mid + 1, fim, val - seg[e]);
}

void query(int pos, int ini, int fim, int p, int q){
	cnt[0] = 0;
	seg[0] = 0;
	if(ini > q || fim < p) return;
	if(ini >= p && fim <= q){
		seg[0] = seg[pos];
		cnt[0] = cnt[pos];
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	query(e, ini, mid, p, q);
	int auxC = cnt[0];
	double auxS = seg[0];
	query(d, mid + 1, fim, p, q);
	cnt[0] += auxC;
	seg[0] += auxS;
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i = 0; i < ord.size(); i++){
      |                 ~~^~~~~~~~~~~~
hiring.cpp: In function 'int bb(int, int, int, double)':
hiring.cpp:70:20: warning: variable 'ret' set but not used [-Wunused-but-set-variable]
   70 |  pair<int, double> ret = make_pair(0, 0);
      |                    ^~~
hiring.cpp: In function 'int main()':
hiring.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |  scanf("%d %lf", &n, &w);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
hiring.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |   scanf("%lf %lf", &s[i], &q[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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