제출 #856034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856034		MilosMilutinovic	Hiring (IOI09_hiring)	C++14	60 / 100	249 ms	13836 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];

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

int query(ll v,ll c){
	v/=c;
	int p=walk(1,1,20000,v);
	if(p==-1) return num[1][1];
	if(p==1) return v/c;
	return get(1,1,20000,1,p-1,1)+(v-get(1,1,20000,1,p-1,0))/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 ans=0,pos=-1;
	for(int _i=1;_i<=n;_i++){
		int i=ord[_i];
		if(s[i]>W){ update(1,1,20000,q[i]); continue; }
		int cur=1+query((W-s[i])*q[i],s[i]);
		if(ans<cur) ans=cur,pos=i;
		update(1,1,20000,q[i]);
	}
	if(ans==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:100:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  100 |  printf("%d\n",res.size());
      |          ~^    ~~~~~~~~~~
      |           |            |
      |           int          std::vector<int>::size_type {aka long unsigned int}
      |          %ld

• Subtask 1: 19 / 30
• Subtask 2: 20 / 28
• Subtask 3: 3 / 6
• Subtask 4: 3 / 6
• Subtask 5: 3 / 6
• Subtask 6: 3 / 6
• Subtask 7: 3 / 6
• Subtask 8: 3 / 6
• Subtask 9: 3 / 6