oj.uz

Submission #433101

# Submission time Handle Problem Language Result Execution time Memory
433101 2021-06-18T20:51:00 Z bigg Hiring (IOI09_hiring) C++14
66 / 100
 663 ms 15428 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,(ll)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 1 ms 1484 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 4 ms 1484 KB Output is correct
7 Partially correct 3 ms 1612 KB Partially correct
8 Correct 5 ms 1612 KB Output is correct
9 Correct 6 ms 1612 KB Output is correct
10 Incorrect 7 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 16 ms 1740 KB Output is correct
14 Correct 18 ms 1844 KB Output is correct
15 Partially correct 20 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 26 ms 2020 KB Partially correct
5 Correct 72 ms 3240 KB Output is correct
6 Incorrect 384 ms 9688 KB Output isn't correct
7 Incorrect 485 ms 12604 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 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 #5
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 #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Partially correct 154 ms 4704 KB Partially correct
2 Partially correct 151 ms 4720 KB Partially correct
3 Incorrect 150 ms 4696 KB Output isn't correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 6988 KB Output is correct
2 Correct 256 ms 6996 KB Output is correct
3 Correct 263 ms 6968 KB Output is correct

Subtask #8
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 608 ms 13884 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 663 ms 15428 KB Output isn't correct
2 Halted 0 ms 0 KB -