Submission #13969

#	Time	Username	Problem	Language	Result	Execution time	Memory
13969		ainta	Be Two Bees (OJUZ10_b2b)	C++98	100 / 100	55 ms	3844 KiB

b2b

#include<stdio.h>
#include<algorithm>
using namespace std;
int n;
double Sh;
struct point{
	double x, y;
	int num;
	bool operator<(const point &p)const{
		return x < p.x;
	}
}w[101000];
double ccw(point a, point b, point c){
	return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
int st[101000], m, p1, p2;
double X, Y, Res = 1e20;
double Gap(int t){
	return (Y + w[st[t]].y) / (X + w[st[t]].x);
}
void Do(int num){
	X = w[num].x, Y = Sh + w[num].y;
	int b = 1, e = m - 1, mid, r = 1;
	while (b <= e){
		mid = (b + e) >> 1;
		if (Gap(mid) >= Gap(mid + 1)){
			b = r = mid + 1;
		}
		else e = mid - 1;
	}
	if (num == st[r]){
		if (m == 1)return;
		if (r == 1 || (r != m && Gap(r + 1)<Gap(r - 1)))r++;
		else r--;
	}
	if (Res > Gap(r)){
		Res = Gap(r);
		p1 = num, p2 = st[r];
	}
}
int main(){
	int i, a, top = 0;
	double My;
	scanf("%d", &n);
	for (i = 1; i <= n; i++){
		scanf("%d", &a); w[i].y = -a;
		w[i].num = i;
		Sh += a;
	}
	for (i = 1; i <= n; i++){
		scanf("%d", &a);
		w[i].x = 1.0 / a;
	}
	sort(w + 1, w + n + 1);
	for (i = 1; i <= n; i++)if (i == 1 || My>w[i].y)My = w[i].y, a = i;
	st[++top] = a;
	for (i = a + 1; i <= n; i++){
		while (top > 1 && ccw(w[st[top - 1]], w[st[top]], w[i]) <= 0)top--;
		st[++top] = i;
	}
	m = top;
	for (i = 1; i <= n; i++){
		Do(i);
	}
	p1 = w[p1].num, p2 = w[p2].num;
	if (p1 > p2)swap(p1, p2);
	printf("%d %d\n", p1, p2);
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 28 / 28
• Subtask 4: 39 / 39