oj.uz

Submission #333829

# Submission time Handle Problem Language Result Execution time Memory
333829 2020-12-07T21:03:14 Z LucaDantas Hiring (IOI09_hiring) C++17
100 / 100
 468 ms 31468 KB 
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int,int>;

#define ff first
#define ss second

constexpr int maxn = 5e5+10, logn = 20;

struct Fraction
{
	ll p, q, id;
	Fraction() {}
	Fraction(ll a, ll b) : p(a), q(b) {}
	Fraction(ll a, ll b, ll c) : p(a), q(b), id(c) {}
	bool operator<(Fraction b) { return p*b.q < q*b.p; }
	bool operator>(Fraction b) { return p*b.q > q*b.p; }
	ll operator*(ll a) {return (a * q) / p;}
	void upd(Fraction a) {
		if(Fraction(p, q) > a)
			p = a.p, q = a.q;
	}
	bool operator==(Fraction a) {
		return p*a.q==q*a.p;
	}
} val[maxn], soma;

struct BIT
{
	ll bit[maxn];
	void upd(int x, int v) {
		for(; x < maxn; x += x&-x)
			bit[x] += v;
	}
	ll query(int x) {
		ll ans = 0;
		for(; x > 0; x -= x&-x)
			ans += bit[x];
		return ans;
	}
	int bs(ll val, ll& come) {
		int pos = 0;
		for(int l = logn; l >= 0; l--) {
			if(pos + (1 << l) >= maxn) continue;
			if(bit[pos + (1 << l)] <= val)
				pos += (1 << l), val -= bit[pos], come += bit[pos];
		}
		return pos;
	}
	void clear() {
		for(int i = 0; i < maxn; i++)
			bit[i] = 0;
	}
} bit, ligados;

int pos[maxn], state[maxn], back[maxn];
pii opa[maxn];

int main() {
	int n; ll w; scanf("%d %lld", &n, &w);
	for(int i = 0, a, b; i < n; i++)
		scanf("%d %d", &a, &b), val[i] = Fraction(a, b, i), opa[i] = {b, i};
	sort(opa, opa+n);
	for(int i = 0; i < n; i++)
		pos[opa[i].ss] = i+1, back[i+1] = opa[i].ss;
	sort(val, val+n);

	ll ans = 0;
	for(int i = 0; i < n; i++) {
		bit.upd(pos[val[i].id], val[i].q);
		ligados.upd(pos[val[i].id], 1);

		ll pay = (val[i] * w), come = 0;
		
		int p = bit.bs(pay, come);
		int here = ligados.query(p);

		if(here == ans)
			soma.upd(Fraction(1ll*come*val[i].p, val[i].q));
		if(here > ans) {
			ans = here;
			soma = Fraction(1ll*come*val[i].p,val[i].q);
		}	
	}

	bit.clear();
	ligados.clear();

	for(int i = 0; i < n; i++) {
		bit.upd(pos[val[i].id], val[i].q);
		ligados.upd(pos[val[i].id], 1);
		state[pos[val[i].id]] = 1;

		ll pay = val[i] * w, come = 0;
		
		int p = bit.bs(pay, come);
		int here = ligados.query(p);
		
		if(here == ans && (Fraction(1ll*come*val[i].p,val[i].q)) == soma) {
			printf("%lld\n", ans);
			for(int j = 1; j <= p; j++)
				if(state[j])
					printf("%d\n", back[j]+1);
			return 0;
		}
	}
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:62:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |  int n; ll w; scanf("%d %lld", &n, &w);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
hiring.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   scanf("%d %d", &a, &b), val[i] = Fraction(a, b, i), opa[i] = {b, i};
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Correct 5 ms 8172 KB Output is correct
3 Correct 5 ms 8172 KB Output is correct
4 Correct 5 ms 8172 KB Output is correct
5 Correct 5 ms 8172 KB Output is correct
6 Correct 6 ms 8300 KB Output is correct
7 Correct 6 ms 8300 KB Output is correct
8 Correct 6 ms 8300 KB Output is correct
9 Correct 8 ms 8428 KB Output is correct
10 Correct 8 ms 8428 KB Output is correct
11 Correct 9 ms 8428 KB Output is correct
12 Correct 10 ms 8556 KB Output is correct
13 Correct 10 ms 8556 KB Output is correct
14 Correct 13 ms 8812 KB Output is correct
15 Correct 14 ms 8812 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Correct 5 ms 8172 KB Output is correct
3 Correct 5 ms 8172 KB Output is correct
4 Correct 18 ms 9068 KB Output is correct
5 Correct 42 ms 10988 KB Output is correct
6 Correct 262 ms 21740 KB Output is correct
7 Correct 347 ms 26604 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 13292 KB Output is correct
2 Correct 91 ms 13324 KB Output is correct
3 Correct 90 ms 13292 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 17260 KB Output is correct
2 Correct 151 ms 17388 KB Output is correct
3 Correct 151 ms 17260 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 28908 KB Output is correct
2 Correct 383 ms 29036 KB Output is correct
3 Correct 389 ms 28908 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 31212 KB Output is correct
2 Correct 465 ms 31340 KB Output is correct
3 Correct 465 ms 31468 KB Output is correct