제출 #856029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856029		MilosMilutinovic	Hiring (IOI09_hiring)	C++14	0 / 100	198 ms	10900 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);
}

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]);
		ans=max(ans,cur);
		update(1,1,20000,q[i]);
	}
	printf("%d\n",ans);
	for(int i=1;i<=ans;i++) printf("%d\n",i);
	return 0;
}

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

hiring.cpp: In function 'int main()':
hiring.cpp:72:12: warning: unused variable 'pos' [-Wunused-variable]
   72 |  int ans=0,pos=-1;
      |            ^~~

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