oj.uz

Submission #387971

# Submission time Handle Problem Language Result Execution time Memory
387971 2021-04-09T15:27:12 Z Bill_00 Hiring (IOI09_hiring) C++14
80 / 100
 1500 ms 59484 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define N 500005
const int c=1000;
using namespace std;
struct node{
	double sum;
	int cnt;
};
node a[4*N];
ll w;
int n,in[N];
double s[N],q[N];
pair<int,pair<double,int> >ans;
vector<pair<double,int> >e;
vector<pair<pair<double,double>,int> >v;
int query(int id,int l,int r,int k){
	if(l==r){
		return l;
	}
	int m=l+r>>1;
	if(a[id*2].cnt>=k){
		return query(id*2,l,m,k);
	}
	else return query(id*2+1,m+1,r,k-a[id*2].cnt);
}
double querysum(int id,int l,int r,int k){
	if(k<l) return 0;
	if(r<=k) return a[id].sum;
	int m=l+r>>1;
	return querysum(id*2,l,m,k)+querysum(id*2+1,m+1,r,k);
}
void update(int id,int l,int r,int k,double u){
	if(l==r){
		a[id].sum+=u;
		++a[id].cnt;
		return;
	}
	int m=l+r>>1;
	if(m>=k) update(id*2,l,m,k,u);
	else update(id*2+1,m+1,r,k,u);
	a[id].sum=a[id*2].sum+a[id*2+1].sum;
	++a[id].cnt;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> w;
	for(int i=1;i<=n;i++){
		cin >> s[i] >> q[i];
		v.pb({{s[i]/q[i],q[i]},i});
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		e.pb({v[i].ff.ss,i});
	}
	sort(e.begin(),e.end());
	for(int i=0;i<e.size();i++){
		in[e[i].ss]=i;
	}
	for(int i=0;i<v.size();i++){
		int l=1,r=i,p=0;
		double x=v[i].ff.ss,y=v[i].ff.ff;
		double z=x*y;
		// cout << l << ' ' << r << ' ' << z << '\n';
		while(l<=r){
			int m=l+r>>1;
			int k=query(1,0,n-1,m);
			double res=querysum(1,0,n-1,k);
			// cout << l << ' ' << r << ' ' << res << '\n';
			if(((res+x)*y)<=w){
				p=m;
				z=max(z,(res+x)*y);
				l=m+1;
				// cout << i << ' ' << l << ' ' << r << ' '<<  z << '\n';
			}
			else r=m-1;
		}
		ans=max(ans,{p,{-z,i}});
		update(1,0,n-1,in[i],x);
	}
	vector<pair<double,int> >t;
	for(int i=0;i<ans.ss.ss;i++){
		t.pb({v[i].ff.ss,v[i].ss});
	}
	sort(t.begin(),t.end());
	cout << ans.ff+1 << '\n';
	cout << v[ans.ss.ss].ss << '\n';
	for(int i=0;i<ans.ff;i++){
		cout << t[i].ss << '\n';
	}
}

Compilation message

hiring.cpp: In function 'int query(int, int, int, int)':
hiring.cpp:24:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |  int m=l+r>>1;
      |        ~^~
hiring.cpp: In function 'double querysum(int, int, int, int)':
hiring.cpp:33:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |  int m=l+r>>1;
      |        ~^~
hiring.cpp: In function 'void update(int, int, int, int, double)':
hiring.cpp:42:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  int m=l+r>>1;
      |        ~^~
hiring.cpp: In function 'int main()':
hiring.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<double, double>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
hiring.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i=0;i<e.size();i++){
      |              ~^~~~~~~~~
hiring.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<double, double>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
hiring.cpp:71:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |    int m=l+r>>1;
      |          ~^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 5 ms 588 KB Output is correct
8 Correct 7 ms 792 KB Output is correct
9 Correct 11 ms 908 KB Output is correct
10 Correct 14 ms 1092 KB Output is correct
11 Correct 16 ms 1172 KB Output is correct
12 Correct 22 ms 1288 KB Output is correct
13 Correct 25 ms 1756 KB Output is correct
14 Correct 39 ms 2108 KB Output is correct
15 Correct 47 ms 2168 KB Output is correct

Subtask #2
20.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 66 ms 3320 KB Output is correct
5 Correct 258 ms 11028 KB Output is correct
6 Execution timed out 1548 ms 45692 KB Time limit exceeded
7 Execution timed out 1590 ms 51976 KB Time limit exceeded

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 16088 KB Output is correct
2 Correct 500 ms 16028 KB Output is correct
3 Correct 504 ms 16096 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 959 ms 29528 KB Output is correct
2 Correct 981 ms 29684 KB Output is correct
3 Correct 954 ms 29660 KB Output is correct

Subtask #8
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1579 ms 55152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1575 ms 59484 KB Time limit exceeded
2 Halted 0 ms 0 KB -