Submission #287377

#	Time	Username	Problem	Language	Result	Execution time	Memory
287377		Namnamseo	Hiring (IOI09_hiring)	C++17	100 / 100	986 ms	63844 KiB

hiring

#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define pb push_back
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }

int n;

struct bunsoo{
	ll mo,ja;
	bunsoo(){ mo=1; ja=0; }
	bunsoo(ll a,ll b){ mo=a; ja=b; }
	bool operator<(const bunsoo& other) const {
		return ja*other.mo < mo*other.ja;
	}
};

struct segtree {
	static const int M=524288;
	ll tree[M*2];
	void upd(int a,ll b){
		a += M;
		while(a) tree[a]+=b, a>>=1;
	}
	ll rangesum(int a,int b){
		ll ret=0;
		a+=M; b+=M;
		while(a<=b){
			if(a%2==1) ret+=tree[a++];
			if(b%2==0) ret+=tree[b--];
			a/=2; b/=2;
		}
		return ret;
	}
	int findpos(ll lim){
		int pos=1;
		ll sl = 0;
		while(pos<M){
			pos *= 2;
			if(sl + tree[pos] <= lim){
				sl += tree[pos];
				++pos;
			}
		}
		pos=1;
		ll cur=0;
		while(pos<M){
			pos *= 2;
			if(cur + tree[pos] < sl){
				cur += tree[pos];
				++pos;
			}
		}
		return pos-M;
	}
} segT, cntT;

struct saram {
	bunsoo gij;
	int s,q;
	int ind;
} Data[500010];
ll w;

vector<int> qs;
set<pp> qset;

int main(){
	read(n,w);

	for(int i=1; i<=n; ++i){
		int s,q; read(s,q);
		qs.pb(q);
		Data[i]={bunsoo(s,q), s, q, i};
	}
	sort(all(qs));
	for(int i=0; i<n; ++i)
		qset.insert({qs[i],i});

	sort(Data+1, Data+n+1, 
	[](const saram& a, const saram& b){
		return a.gij < b.gij;
	});

	int ans = -1;
	int ans_ind = -1;
	bunsoo ans_cost(1, 2e9);

	for(int i=n; 1<=i; --i){
		auto it = qset.lower_bound({Data[i].q,0});
		int qi = it->second;
		qset.erase(it);
//		printf("Updating: %d\n", qi);

		segT.upd(qi, Data[i].q);
		cntT.upd(qi, 1);
		
		ll up_lim = w*Data[i].q / Data[i].s;
//		printf("limit %lld\n", up_lim);

		int t = segT.findpos(up_lim);
//		printf("t %d\n", t);
		int cnt = cntT.rangesum(0, t);
		ll qs = segT.rangesum(0, t);
//		printf("cnt %d; qs %lld\n", cnt, qs);

//		putchar(10);

		bunsoo tmp(Data[i].q, qs*Data[i].s);
		if(ans < cnt){
			ans = cnt;
			ans_cost = tmp;
			ans_ind = i;
		} else if(ans == cnt){
			if(tmp < ans_cost){
				ans_cost = tmp;
				ans_ind = i;
			}
		}
	}
	printf("%d\n", ans);
	sort(Data+ans_ind, Data+n+1, [](const saram& a, const saram& b){
		return a.q < b.q;
	});
	for(int i=ans_ind; i<ans_ind + ans; ++i){
		printf("%d\n", Data[i].ind);
	}
	return 0;
}

Compilation message (stderr)

hiring.cpp: In function 'void read(int&)':
hiring.cpp:8:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 | void read(int& x){ scanf("%d",&x); }
      |                    ~~~~~^~~~~~~~~
hiring.cpp: In function 'void read(ll&)':
hiring.cpp:9:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 | void read(ll& x){ scanf("%lld",&x); }
      |                   ~~~~~^~~~~~~~~~~

• 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