Submission #536274

#	Time	Username	Problem	Language	Result	Execution time	Memory
536274		lovrot	Hiring (IOI09_hiring)	C++11	100 / 100	608 ms	59068 KiB

hiring

#include <bits/stdc++.h> 
#include <unistd.h>

#define X first
#define Y second
#define pii pair<int, int>
#define pb push_back
#define vec vector
#define siz size()
#define pri(i, poc, n, pov) for(int i = (int) poc; i < (int) n; i += (int) pov)
#define od(i, poc, n, pov) for(int i = (int) poc; i > (int) n; i -= (int) pov)

using namespace std;
                    
const int LOG = 20;
const int OFF = (1 << LOG);

struct skup{ 
	double sum = 0;
	int n = 0;
} tour[OFF * 2];
skup zero;

int n, tourpos[OFF];
bool out[OFF];

double s[OFF], q[OFF], w;
vec<pair<double, int>> q_v, v, q_out;

skup merge(skup a, skup b){ 
	skup ret;
	ret.sum = a.sum + b.sum;
	ret.n = a.n + b.n;
	return ret;
}

void update(int x, double v){ 
	x += OFF;
	tour[x].sum = v;
	tour[x].n = 1;

	x >>= 1;
	while(x){ 
		tour[x] = merge(tour[x * 2], tour[x * 2 + 1]);
		x >>= 1;
	}
}

skup query(int v, int lo = 0, int hi = OFF, int x = 1){ 
	if(tour[x].sum <= v)
		return tour[x];
	if(x >= OFF)
		return zero;

	int mi = (lo + hi) / 2;

	if(tour[x * 2].sum >= v)
		return query(v, lo, mi, x * 2);
	return merge(tour[x * 2], query(v - tour[x * 2].sum, mi, hi, x * 2 + 1));
}

int main(){ 
	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	cout.tie(0);
	setprecision(9);

	cin >> n >> w;

	pri(i, 0, n, 1){ 
		cin >> s[i] >> q[i];
		v.pb({s[i] / q[i], i});
		q_v.pb({q[i], i});
	}	
	sort(v.begin(), v.end()); 
	sort(q_v.begin(), q_v.end());

	pri(i, 0, n, 1){ 
		tourpos[q_v[i].Y] = i;
	}

	int mx = -1, mxi = 0; 
	double mnw = w;

	pri(i, 0, n, 1){
		int x = v[i].Y; 
		double t = v[i].X;
		double zb = w / t;
		double qq = zb - q[x];

		skup res = query(qq);
		res.n++;
		res.sum += q[x];

		if(res.n >= mx){ 
			if(res.n == 2){
				//cout << x << " " << t * res.sum << "\n";
			}
			if(mx == res.n && mnw > t * res.sum){ 
				mxi = x;
				mnw = t * res.sum;
			} 
			if(res.n > mx){
				mx = res.n;
				mxi = x;
				mnw = t * res.sum;
			}

		}
		update(tourpos[x], q[x]);
	}

	double zb = q[mxi];
	double t = s[mxi] / q[mxi];

	cout << mx << "\n";

	out[mxi] = true;
	pri(i, 0, n, 1){ 
		if(mxi == v[i].Y)
			break;
		q_out.pb({q[v[i].Y], v[i].Y});
	}
	sort(q_out.begin(), q_out.end());
	for(pair<double, int> i : q_out){ 
		if(t * (i.X + zb) > w)
			break;
		out[i.Y] = true;
		zb += i.X;
	}

	pri(i, 0, n, 1){ 
		if(out[i])
			cout << i + 1 << "\n";
	}
	return 0;
}

• 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