Submission #433098

#	Time	Username	Problem	Language	Result	Execution time	Memory
433098		bigg	Hiring (IOI09_hiring)	C++14	66 / 100	619 ms	15500 KiB

hiring

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10;
const int MAXQ =  2e4 + 10;
typedef long ll;

#define esq(x) x << 1 
#define dir(x) (x<<1) | 1
#define mid(x,y,t) ((x+y)>>1) + t
#define debug(args...) //debug(stderr, args)

int MAX = 2e4 + 10;
bool sorttwo;
struct worker{
	int id;
	double q, s;

	bool operator < (worker w) const{
		
		return s/q < w.s/w.q; 
		
	}
} workers[MAXN];

struct nodeseg{
	ll qaqui;
	int act;
	bool f;
	nodeseg(ll _q = 0, int _a = 0, bool _f = 0){
		qaqui = _q;
		act = _a;
		f = _f;
	}
	nodeseg operator + (nodeseg b){
		if(f && b.f) return nodeseg(0,0,1);
		if(f) return b;
		if(b.f) return *this;
		nodeseg ans = nodeseg(qaqui + b.qaqui, act + b.act, 0);
		return ans;
	}
} seg[4*MAXQ];

void update(int node, int x, int y, int q){
	debug(stderr, "oiu\n");
	if(x > q || y < q) return;
	if(x == y){
		seg[node].act++;
		seg[node].qaqui += q;
		return;
	}
	update(esq(node), x, mid(x,y,0), q);
	update(dir(node), mid(x,y,1), y, q);
	seg[node] = seg[esq(node)] + seg[dir(node)];
}

nodeseg query(int node, int x, int y, int l, int r){
	debug(stderr, "oiq\n");
	if(x > r || y < l) return nodeseg(0,0,1);
	if(x >= l && y <= r) return seg[node];
	nodeseg e = query(esq(node), x, mid(x,y,0), l, r);
	nodeseg d = query(dir(node), mid(x,y,1), y, l, r);
	return e + d;
}

int bb(int node, int x, int y, ll q){
	debug(stderr, "oi\n");
	debug("BB %lld\n", q);
	if(x == y) return x;
	if(seg[esq(node)].qaqui >= q){
		return bb(esq(node), x, mid(x,y,0), q);
	}
	return bb(dir(node), mid(x,y,1), y, q - seg[esq(node)].qaqui);
}

bool comp(worker i, worker j){
	return i.q < j.q;
}
double w;
int n;

int main(){
	scanf("%d %lf", &n, &w);

	for(int i = 1; i <= n; i++){
		scanf("%lf %lf", &workers[i].s, &workers[i].q );
		workers[i].q = (int)workers[i].q;
		workers[i].id = i;
		
	}
	sort(workers + 1, workers + 1 + n);
	
	double kfd;
	int qtd = 0;
	double tots = 1e18;
	for(int i = 1; i <= n; i++){
		
		double k = workers[i].s/workers[i].q;
		double aq = w/k;
		int tot = 0;
		double totq = 0;
		debug("%d %lf %lf\n", workers[i].id, k, aq);
		debug(stderr, "%d afs\n", i);
		debug(stderr, "%lf", workers[i].q);
		update(1,1,MAX,workers[i].q);

		if(seg[1].qaqui <= aq){
			tot = seg[1].act;
			totq = seg[1].qaqui;
		}else{
			int id = bb(1,1,MAX,(int)aq) - 1;
			tot = query(1,1,MAX,1,id).act;
			totq = query(1,1,MAX,1,id).qaqui;
		}
		if(tot == qtd){
			debug("T: %d\n", tot);
			if(tots > totq*k ){
				kfd = k;
				tots =totq*k;
			}
		}
		if(tot > qtd){
			debug("T: %d\n", tot);
			kfd = k;
			qtd = tot;
			tots = totq*k;
		}
	}
	vector<int> ans;
	sorttwo = 1;
	sort(workers + 1, workers + 1 + n, comp);
	double aq = 0;
	for(int j = 1; j <= n; j++){
		if(workers[j].q* kfd < workers[j].s) continue;
		aq += kfd*workers[j].q;
		if(aq > w){
			break;
		}
		ans.push_back(workers[j].id);
	}
	printf("%d\n",(int)ans.size() );
	for(int i : ans) printf("%d\n", i);
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  scanf("%d %lf", &n, &w);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
hiring.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%lf %lf", &workers[i].s, &workers[i].q );
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hiring.cpp:133:18: warning: 'kfd' may be used uninitialized in this function [-Wmaybe-uninitialized]
  133 |   if(workers[j].q* kfd < workers[j].s) continue;
      |      ~~~~~~~~~~~~^~~~~

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