제출 #856038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856038		MilosMilutinovic	Hiring (IOI09_hiring)	C++14	100 / 100	257 ms	14264 KiB

hiring

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 30
• Subtask 2: 28 / 28
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6