oj.uz

Submission #287377

# Submission time Handle Problem Language Result Execution time Memory
287377 2020-08-31T16:33:31 Z Namnamseo Hiring (IOI09_hiring) C++17
100 / 100
 986 ms 63844 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define pb push_back
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }

int n;

struct bunsoo{
	ll mo,ja;
	bunsoo(){ mo=1; ja=0; }
	bunsoo(ll a,ll b){ mo=a; ja=b; }
	bool operator<(const bunsoo& other) const {
		return ja*other.mo < mo*other.ja;
	}
};

struct segtree {
	static const int M=524288;
	ll tree[M*2];
	void upd(int a,ll b){
		a += M;
		while(a) tree[a]+=b, a>>=1;
	}
	ll rangesum(int a,int b){
		ll ret=0;
		a+=M; b+=M;
		while(a<=b){
			if(a%2==1) ret+=tree[a++];
			if(b%2==0) ret+=tree[b--];
			a/=2; b/=2;
		}
		return ret;
	}
	int findpos(ll lim){
		int pos=1;
		ll sl = 0;
		while(pos<M){
			pos *= 2;
			if(sl + tree[pos] <= lim){
				sl += tree[pos];
				++pos;
			}
		}
		pos=1;
		ll cur=0;
		while(pos<M){
			pos *= 2;
			if(cur + tree[pos] < sl){
				cur += tree[pos];
				++pos;
			}
		}
		return pos-M;
	}
} segT, cntT;

struct saram {
	bunsoo gij;
	int s,q;
	int ind;
} Data[500010];
ll w;

vector<int> qs;
set<pp> qset;

int main(){
	read(n,w);

	for(int i=1; i<=n; ++i){
		int s,q; read(s,q);
		qs.pb(q);
		Data[i]={bunsoo(s,q), s, q, i};
	}
	sort(all(qs));
	for(int i=0; i<n; ++i)
		qset.insert({qs[i],i});

	sort(Data+1, Data+n+1, 
	[](const saram& a, const saram& b){
		return a.gij < b.gij;
	});

	int ans = -1;
	int ans_ind = -1;
	bunsoo ans_cost(1, 2e9);

	for(int i=n; 1<=i; --i){
		auto it = qset.lower_bound({Data[i].q,0});
		int qi = it->second;
		qset.erase(it);
//		printf("Updating: %d\n", qi);

		segT.upd(qi, Data[i].q);
		cntT.upd(qi, 1);
		
		ll up_lim = w*Data[i].q / Data[i].s;
//		printf("limit %lld\n", up_lim);

		int t = segT.findpos(up_lim);
//		printf("t %d\n", t);
		int cnt = cntT.rangesum(0, t);
		ll qs = segT.rangesum(0, t);
//		printf("cnt %d; qs %lld\n", cnt, qs);

//		putchar(10);

		bunsoo tmp(Data[i].q, qs*Data[i].s);
		if(ans < cnt){
			ans = cnt;
			ans_cost = tmp;
			ans_ind = i;
		} else if(ans == cnt){
			if(tmp < ans_cost){
				ans_cost = tmp;
				ans_ind = i;
			}
		}
	}
	printf("%d\n", ans);
	sort(Data+ans_ind, Data+n+1, [](const saram& a, const saram& b){
		return a.q < b.q;
	});
	for(int i=ans_ind; i<ans_ind + ans; ++i){
		printf("%d\n", Data[i].ind);
	}
	return 0;
}

Compilation message

hiring.cpp: In function 'void read(int&)':
hiring.cpp:8:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 | void read(int& x){ scanf("%d",&x); }
      |                    ~~~~~^~~~~~~~~
hiring.cpp: In function 'void read(ll&)':
hiring.cpp:9:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 | void read(ll& x){ scanf("%lld",&x); }
      |                   ~~~~~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16256 KB Output is correct
2 Correct 9 ms 16128 KB Output is correct
3 Correct 9 ms 16128 KB Output is correct
4 Correct 9 ms 16128 KB Output is correct
5 Correct 10 ms 16128 KB Output is correct
6 Correct 11 ms 16256 KB Output is correct
7 Correct 14 ms 16256 KB Output is correct
8 Correct 12 ms 16384 KB Output is correct
9 Correct 14 ms 16512 KB Output is correct
10 Correct 14 ms 16512 KB Output is correct
11 Correct 16 ms 16640 KB Output is correct
12 Correct 17 ms 16888 KB Output is correct
13 Correct 19 ms 16896 KB Output is correct
14 Correct 26 ms 17280 KB Output is correct
15 Correct 26 ms 17536 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16128 KB Output is correct
2 Correct 9 ms 16128 KB Output is correct
3 Correct 9 ms 16128 KB Output is correct
4 Correct 33 ms 18048 KB Output is correct
5 Correct 73 ms 22256 KB Output is correct
6 Correct 610 ms 44652 KB Output is correct
7 Correct 562 ms 54116 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16256 KB Output is correct
2 Correct 9 ms 16128 KB Output is correct
3 Correct 12 ms 16128 KB Output is correct

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 26864 KB Output is correct
2 Correct 203 ms 26864 KB Output is correct
3 Correct 207 ms 26996 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 34920 KB Output is correct
2 Correct 260 ms 34964 KB Output is correct
3 Correct 254 ms 34924 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 58984 KB Output is correct
2 Correct 768 ms 58980 KB Output is correct
3 Correct 768 ms 58932 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 986 ms 63844 KB Output is correct
2 Correct 973 ms 63716 KB Output is correct
3 Correct 981 ms 63816 KB Output is correct