Submission #536240

#	Time	Username	Problem	Language	Result	Execution time	Memory
536240		drkarlicio2107	Hiring (IOI09_hiring)	C++14	80 / 100	1080 ms	65536 KiB

hiring

#include <bits/stdc++.h>
using namespace std; vector < pair < pair <long double, int>, pair <long double, long double> > > k; map <long double, int> saz; vector < pair <long double, int> > qi; map <int, long double> ob; long double min_w;
vector < pair < int, int > > sol;
const int OFF = (1 << 20); 
long double tour[2*OFF];
void update(int x, long double v) {
    x+=OFF;
    tour[x]=v;
    x/=2;
    while (x) {
        tour[x]=tour[x*2]+tour[x*2+1];
        x/=2;
    }
	return;
}
pair<int, long double> query(int lo=0, int hi=OFF-1, int x=1, long double now=0) {
    if (lo==hi) return {x-OFF, now};
    int mid=(lo+hi)/2;
    long double le=tour [x*2];
    long double de=tour [x*2+1];
    if (le+now>min_w) return query(lo, mid, x*2, now);
    else return query(mid+1, hi, x*2+1, le+now);
}
int fen[OFF+10];
void dodaj(int a, int v){
	for (a; a<OFF+10; a+= a & -a) fen[a]+=v;
}
int ispis(int a){
	if (a==0 || a==-1) return 0;
	int izlaz=0;
	for (a; a>0; a-= a & -a) izlaz+=fen[a];
	return izlaz;
}
int main(){
	int n; long double w; cin >> n >> w;
	for (int i=0; i<n; i++){
		long double s, q; cin >> s >> q;
		long double x=s/q;
		k.push_back({{x, i}, {s, q}});
		qi.push_back({q, i}); 
	}
	sort (qi.begin (), qi.end ());
	sort (k.begin (), k.end ());
	int ind=1;
	for (int i=0; i<qi.size(); i++){
		//cout << qi [i] << endl;
		saz [qi[i].second]=ind; ind++;
	}
	int max_ans=-1, res; long double platit=0;
	for (int i=0; i<n; i++){
		long double x=k[i].first.first;
		min_w=w/x;
		int ind=saz [k[i].first.second];
		//cout << x << " " << min_w << " " << ind << " " << k[i].first.second << endl;
		long double val=k[i].second.second;
		dodaj (ind, 1);
		update (ind, val);
		int gr=query ().first;
		long double zb=query ().second;
		//cout << zb*x << endl;
		if (ispis (gr-1)>max_ans || (ispis (gr-1)==max_ans && zb*x<platit)){
			max_ans=ispis (gr-1); platit=zb*x; res=i;
		}
	}
	//cout << res << endl;
	for (int i=0; i<res+1; i++){
		int ind1=k[i].first.second;
		sol.push_back((make_pair(saz[k[i].first.second], ind1)));
	}
	sort (sol.begin(), sol.end());
	cout << max_ans << endl;
	for (int i=0; i<max_ans; i++) cout << sol [i].second+1 << endl;
}

Compilation message (stderr)

hiring.cpp: In function 'std::pair<int, long double> query(int, int, int, long double)':
hiring.cpp:20:17: warning: unused variable 'de' [-Wunused-variable]
   20 |     long double de=tour [x*2+1];
      |                 ^~
hiring.cpp: In function 'void dodaj(int, int)':
hiring.cpp:26:7: warning: statement has no effect [-Wunused-value]
   26 |  for (a; a<OFF+10; a+= a & -a) fen[a]+=v;
      |       ^
hiring.cpp: In function 'int ispis(int)':
hiring.cpp:31:7: warning: statement has no effect [-Wunused-value]
   31 |  for (a; a>0; a-= a & -a) izlaz+=fen[a];
      |       ^
hiring.cpp: In function 'int main()':
hiring.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i=0; i<qi.size(); i++){
      |                ~^~~~~~~~~~
hiring.cpp:66:17: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |  for (int i=0; i<res+1; i++){
      |                ~^~~~~~

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