oj.uz

Submission #303444

# Submission time Handle Problem Language Result Execution time Memory
303444 2020-09-20T10:14:21 Z Hemimor Hiring (IOI09_hiring) C++14
100 / 100
 1370 ms 65536 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 6 ms 1024 KB Output is correct
11 Correct 7 ms 1152 KB Output is correct
12 Correct 9 ms 1408 KB Output is correct
13 Correct 10 ms 1664 KB Output is correct
14 Correct 16 ms 2048 KB Output is correct
15 Correct 17 ms 2292 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 28 ms 3320 KB Output is correct
5 Correct 82 ms 10360 KB Output is correct
6 Correct 747 ms 44792 KB Output is correct
7 Correct 940 ms 55292 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 15480 KB Output is correct
2 Correct 210 ms 15480 KB Output is correct
3 Correct 218 ms 15608 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 27768 KB Output is correct
2 Correct 355 ms 27768 KB Output is correct
3 Correct 357 ms 27768 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1042 ms 60816 KB Output is correct
2 Correct 994 ms 60980 KB Output is correct
3 Correct 1059 ms 60792 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1370 ms 65536 KB Output is correct
2 Correct 1358 ms 65536 KB Output is correct
3 Correct 1311 ms 65536 KB Output is correct