oj.uz

Submission #433098

# Submission time Handle Problem Language Result Execution time Memory
433098 2021-06-18T20:49:08 Z bigg Hiring (IOI09_hiring) C++14
66 / 100
 619 ms 15500 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 2 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 5 ms 1484 KB Output is correct
7 Partially correct 4 ms 1612 KB Partially correct
8 Correct 6 ms 1612 KB Output is correct
9 Correct 8 ms 1652 KB Output is correct
10 Incorrect 8 ms 1612 KB Output isn't correct
11 Correct 9 ms 1612 KB Output is correct
12 Correct 9 ms 1740 KB Output is correct
13 Correct 13 ms 1720 KB Output is correct
14 Correct 17 ms 1840 KB Output is correct
15 Partially correct 22 ms 1900 KB Partially correct

Subtask #2
16.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Partially correct 1 ms 1484 KB Partially correct
3 Correct 1 ms 1484 KB Output is correct
4 Partially correct 32 ms 2012 KB Partially correct
5 Correct 71 ms 3228 KB Output is correct
6 Incorrect 432 ms 9720 KB Output isn't correct
7 Incorrect 493 ms 12580 KB Output isn't correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 2 ms 1484 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1484 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 3 ms 1484 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 3 ms 1484 KB Output is correct

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 188 ms 4704 KB Partially correct
2 Partially correct 146 ms 4704 KB Partially correct
3 Incorrect 162 ms 4736 KB Output isn't correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 6984 KB Output is correct
2 Correct 245 ms 6980 KB Output is correct
3 Correct 244 ms 6988 KB Output is correct

Subtask #8
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 555 ms 13896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 619 ms 15500 KB Output isn't correct
2 Halted 0 ms 0 KB -