| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 13969 |
2015-04-24T16:59:05 Z |
ainta |
Be Two Bees (OJUZ10_b2b) |
C++ |
|
55 ms |
3844 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 4 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 5 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 6 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 7 |
Correct |
0 ms |
3844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 4 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 5 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 6 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 7 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 8 |
Correct |
0 ms |
3844 KB |
Output is correct |
| 9 |
Correct |
0 ms |
3844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
3844 KB |
Output is correct |
| 2 |
Correct |
25 ms |
3844 KB |
Output is correct |
| 3 |
Correct |
45 ms |
3844 KB |
Output is correct |
| 4 |
Correct |
45 ms |
3844 KB |
Output is correct |
| 5 |
Correct |
46 ms |
3844 KB |
Output is correct |
| 6 |
Correct |
15 ms |
3844 KB |
Output is correct |
| 7 |
Correct |
31 ms |
3844 KB |
Output is correct |
| 8 |
Correct |
46 ms |
3844 KB |
Output is correct |
| 9 |
Correct |
19 ms |
3844 KB |
Output is correct |
| 10 |
Correct |
43 ms |
3844 KB |
Output is correct |
| 11 |
Correct |
20 ms |
3844 KB |
Output is correct |
| 12 |
Correct |
26 ms |
3844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
3844 KB |
Output is correct |
| 2 |
Correct |
50 ms |
3844 KB |
Output is correct |
| 3 |
Correct |
43 ms |
3844 KB |
Output is correct |
| 4 |
Correct |
8 ms |
3844 KB |
Output is correct |
| 5 |
Correct |
53 ms |
3844 KB |
Output is correct |
| 6 |
Correct |
55 ms |
3844 KB |
Output is correct |
| 7 |
Correct |
41 ms |
3844 KB |
Output is correct |
| 8 |
Correct |
52 ms |
3844 KB |
Output is correct |
| 9 |
Correct |
18 ms |
3844 KB |
Output is correct |
| 10 |
Correct |
33 ms |
3844 KB |
Output is correct |
| 11 |
Correct |
26 ms |
3844 KB |
Output is correct |
| 12 |
Correct |
51 ms |
3844 KB |
Output is correct |
| 13 |
Correct |
30 ms |
3844 KB |
Output is correct |
| 14 |
Correct |
38 ms |
3844 KB |
Output is correct |
| 15 |
Correct |
46 ms |
3844 KB |
Output is correct |
| 16 |
Correct |
52 ms |
3844 KB |
Output is correct |
| 17 |
Correct |
36 ms |
3844 KB |
Output is correct |
