Submission #303444

#	Time	Username	Problem	Language	Result	Execution time	Memory
303444		Hemimor	Hiring (IOI09_hiring)	C++14	100 / 100	1370 ms	65536 KiB

hiring

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Segment_Tree{
	private:
	int n;
	vi num;
	vl date;
	public:
	Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		num=vi(2*n-1);
		date=vl(2*n-1);
	}
	void Update(int k,ll x){
		k+=n-1;
		date[k]+=x;
		num[k]++;
		while(k>0){
			k=(k-1)/2;
			date[k]=date[k*2+1]+date[k*2+2];
			num[k]=num[2*k+1]+num[2*k+2];
		}
	}
	int Query(ll x,int &t,ll &sm){
		sm=0;
		t=0;
		int k=0;
		while(k<n-1){
			if(sm+date[2*k+1]<=x){
				sm+=date[2*k+1];
				t+=num[2*k+1];
				k=2*k+2;
			}
			else k=2*k+1;
		}
		return k-n+1;
	}
	int Open(int k){return date[k+n-1];}
};

int n;
ll m;

bool f(ll x,ll y,ll X,ll Y){
	if(x/y<X/Y) return 1;
	if(x/y>X/Y) return 0;
	x%=y,X%=Y;
	return x*Y<X*y;
}

int main(){
	scanf("%d%lld",&n,&m);
	vector<pair<pll,int>> a(n);
	vp b(n);
	map<P,int> mp;
	Segment_Tree st(n);
	int mxnum=0,I=0,id=-1;
	ll resmu=0,resml=1;
	pair<pll,int> res={{0,0},-1};
	for(int i=0;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		a[i]={{x,y},i};
		b[i]={y,i};
	}
	sort(b.begin(),b.end());
	sort(a.begin(),a.end(),[](pair<pll,int> pp,pair<pll,int> qq){
		pll p=pp.first,q=qq.first;
		return p.first*q.second<q.first*p.second;
	});
	for(int i=0;i<n;i++) mp[b[i]]=i;
	for(int i=0;i<n;i++){
		pll p=a[i].first;
		ll x=p.first,y=p.second;
		st.Update(mp[{y,a[i].second}],y);
		ll sm=0;
		int num=0;
		int k=st.Query(m*y/x,num,sm);
		ll smu=sm*x,sml=y;
//		cout<<i<<' '<<x<<' '<<y<<' '<<mp[{y,a[i].second}]<<' '<<num<<' '<<sm<<' '<<k<<endl;
		if(mxnum<num||mxnum==num&&f(smu,sml,resmu,resml)){
			mxnum=num;
			resmu=smu;
			resml=sml;
			I=i,id=k;
		}
	}
	printf("%d\n",mxnum);
//	cout<<resmu<<' '<<resml<<endl;
//	cout<<id<<endl;
	if(mxnum==0) return 0;
	for(int i=0;i<=I;i++){
//		cout<<a[i].first.first<<' '<<a[i].first.second<<' '<<a[i].second<<endl;
//		cout<<mp[{a[i].first.second,a[i].second}]<<endl;
		if(mp[{a[i].first.second,a[i].second}]<id) printf("%d\n",a[i].second+1);
	}
}

Compilation message (stderr)

hiring.cpp: In function 'int main()':
hiring.cpp:117:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  117 |   if(mxnum<num||mxnum==num&&f(smu,sml,resmu,resml)){
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hiring.cpp:95:16: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   95 |  pair<pll,int> res={{0,0},-1};
      |                ^~~
hiring.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |  scanf("%d%lld",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~
hiring.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~

• 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