oj.uz

Submission #856038

# Submission time Handle Problem Language Result Execution time Memory
856038 2023-10-02T15:22:15 Z MilosMilutinovic Hiring (IOI09_hiring) C++14
100 / 100
 257 ms 14264 KB 
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,s[500005],q[500005],ord[500005];
ll W,num[80005][2];

struct frac{
	ll p,q;
	bool operator< (const frac f){
		return p*f.q<f.p*q;
	}
};

bool cmp(int i,int j){ return s[i]*q[j]<s[j]*q[i]; }

void build(int id,int l,int r){
	num[id][0]=0;
	num[id][1]=0;
	if(l==r) return;
	int mid=(l+r)/2;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
}

void update(int id,int l,int r,int p){
	if(l==r) return (void)(num[id][0]+=p,num[id][1]+=1);
	int mid=(l+r)/2;
	if(p<=mid) update(id<<1,l,mid,p);
	else update(id<<1|1,mid+1,r,p);
	num[id][0]=num[id<<1][0]+num[id<<1|1][0];
	num[id][1]=num[id<<1][1]+num[id<<1|1][1];
}

int walk(int id,int l,int r,ll x){
	if(l==r) return num[id][0]>=x?l:-1;
	int mid=(l+r)/2;
	if(num[id<<1][0]>=x) return walk(id<<1,l,mid,x);
	else return walk(id<<1|1,mid+1,r,x-num[id<<1][0]);
}

ll get(int id,int l,int r,int ql,int qr,int t){
	if(ql<=l&&r<=qr) return num[id][t];
	int mid=(l+r)/2;
	if(qr<=mid) return get(id<<1,l,mid,ql,qr,t);
	else if(ql>mid) return get(id<<1|1,mid+1,r,ql,qr,t);
	else return get(id<<1,l,mid,ql,qr,t)+get(id<<1|1,mid+1,r,ql,qr,t);
}

pair<int,ll> query(ll v,ll c){
	v/=c;
	int p=walk(1,1,20000,v);
	if(p==-1) return mp(num[1][1],num[1][0]);
	if(p==1) return mp(v/c,v/c);
	return mp(get(1,1,20000,1,p-1,1)+(v-get(1,1,20000,1,p-1,0))/p,get(1,1,20000,1,p-1,0)+((v-get(1,1,20000,1,p-1,0))/p)*p);
}

int main(){
	n=readint(); W=readint();
	for(int i=1;i<=n;i++) s[i]=readint(),q[i]=readint();
	for(int i=1;i<=n;i++) ord[i]=i;
	sort(ord+1,ord+n+1,cmp);
	build(1,1,20000);
	int pos=-1;
	int cnt=0;
	frac ans;
	for(int _i=1;_i<=n;_i++){
		int i=ord[_i];
		if(s[i]>W){ update(1,1,20000,q[i]); continue; }
		auto qv=query((W-s[i])*q[i],s[i]);
		qv.fi+=1;
		if(qv.fi>cnt){
			cnt=qv.fi;
			pos=i;
			ans.p=s[i]*(qv.se+q[i]);
			ans.q=q[i];
		}else if(qv.fi==cnt){
			frac f;
			f.p=s[i]*(qv.se+q[i]);
			f.q=q[i];
			if(f<ans){
				ans=f;
				pos=i;
			}
		}
		update(1,1,20000,q[i]);
	}
	if(cnt==0){
		printf("0");
		return 0;
	}
	vector<pii> vec;
	vector<int> res;
	for(int _i=1;_i<=n;_i++){
		int i=ord[_i];
		if(i==pos){
			res.pb(i);
			sort(vec.begin(),vec.end());
			W-=s[i];
			W*=q[i];
			W/=s[i];
			for(auto&p:vec) if(W>=p.fi) W-=p.fi,res.pb(p.se);
			break;
		}
		vec.pb(mp(q[i],i));
	}
	sort(res.begin(),res.end());
	printf("%d\n",res.size());
	for(int i=0;i<(int)res.size();i++) printf("%d\n",res[i]);
	return 0;
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:123:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  123 |  printf("%d\n",res.size());
      |          ~^    ~~~~~~~~~~
      |           |            |
      |           int          std::vector<int>::size_type {aka long unsigned int}
      |          %ld
hiring.cpp:26:19: warning: 'ans.frac::p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |   return p*f.q<f.p*q;
      |                ~~~^~
hiring.cpp:81:7: note: 'ans.frac::p' was declared here
   81 |  frac ans;
      |       ^~~
hiring.cpp:26:11: warning: 'ans.frac::q' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |   return p*f.q<f.p*q;
      |          ~^~~~
hiring.cpp:81:7: note: 'ans.frac::q' was declared here
   81 |  frac ans;
      |       ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6744 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 4 ms 6748 KB Output is correct
12 Correct 4 ms 6744 KB Output is correct
13 Correct 5 ms 6772 KB Output is correct
14 Correct 7 ms 7004 KB Output is correct
15 Correct 7 ms 6748 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 10 ms 6900 KB Output is correct
5 Correct 18 ms 7004 KB Output is correct
6 Correct 149 ms 10336 KB Output is correct
7 Correct 178 ms 13240 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 7904 KB Output is correct
2 Correct 55 ms 7904 KB Output is correct
3 Correct 56 ms 8388 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 9176 KB Output is correct
2 Correct 87 ms 9240 KB Output is correct
3 Correct 87 ms 9156 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 14012 KB Output is correct
2 Correct 207 ms 13940 KB Output is correct
3 Correct 211 ms 14116 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 14144 KB Output is correct
2 Correct 243 ms 14264 KB Output is correct
3 Correct 251 ms 13780 KB Output is correct