oj.uz

Submission #14041

# Submission time Handle Problem Language Result Execution time Memory
14041 2015-04-25T15:07:44 Z kriii Be Two Bees (OJUZ10_b2b) C++14
100 / 100
 82 ms 6840 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

struct rat{
	rat(){a = 0; b = 1;}
	rat(long long a_, long long b_){
		a = a_; b = b_;
	}
	long long a,b;
	bool operator <(const rat t) const{
		return a * t.b < b * t.a;
	}
};

vector<pair<int, int> > line[100010];
int N,H[100010],T[100010],V[100010],Z; long long S;
int p=-1,q=-1; long long A[5],B[5];

void mul(long long *x, long long p)
{
	for (int i=0;i<5;i++) x[i] *= p;
	for (int i=0;i<5;i++){
		if (x[i] >= 10000000){
			x[i+1] += x[i] / 10000000;
			x[i] %= 10000000;
		}
	}
}

void put(int i, int j)
{
	if (i > j) swap(i,j);
	if (p == -1){
		p = i; q = j;
		return;
	}
	for (int k=0;k<5;k++) A[k] = B[k] = 0;
	A[0] = B[0] = 1;
	mul(A,S-H[i]-H[j]);
	mul(A,T[i]);
	mul(A,T[j]);
	mul(B,T[i]+T[j]);
	mul(B,S-H[p]-H[q]);
	mul(B,T[p]);
	mul(B,T[q]);
	mul(A,T[p]+T[q]);

	for (int k=4;k>=0;k--){
		if (A[k] != B[k]){
			if (A[k] < B[k]){ p = i; q = j; }
			break;
		}
	}
}

bool bad(long long t1, long long h1, long long t2, long long h2, long long t3, long long h3)
{
	return t2 * t3 * (h2 - h3) + t3 * t1 * (h3 - h1) + t1 * t2 * (h1 - h2) <= t1 * t2 * t3;
}

int main()
{
	scanf ("%d",&N);
	for (int i=0;i<N;i++) scanf ("%d",&H[i]), S += H[i];
	for (int j=0;j<N;j++) scanf ("%d",&T[j]), line[T[j]].push_back(make_pair(H[j],j));

	for (int i=100000;i>=1;i--) if (!line[i].empty()){
		sort(line[i].rbegin(),line[i].rend());
		if (line[i].size() >= 2){
			put(line[i][0].second,line[i][1].second);
		}

		int x = line[i][0].second;
		while (Z >= 2){
			if (bad(T[V[Z-2]],H[V[Z-2]],T[V[Z-1]],H[V[Z-1]],T[x],H[x])){
				put(V[--Z],x);
			}
			else break;
		}
		V[Z++] = x;
		if (Z >= 2){
			put(V[Z-2],V[Z-1]);
		}
	}

	printf ("%d %d\n",p+1,q+1);

	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4728 KB Output is correct
2 Correct 0 ms 4728 KB Output is correct
3 Correct 0 ms 4728 KB Output is correct
4 Correct 0 ms 4728 KB Output is correct
5 Correct 0 ms 4728 KB Output is correct
6 Correct 0 ms 4728 KB Output is correct
7 Correct 0 ms 4728 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4728 KB Output is correct
2 Correct 2 ms 4728 KB Output is correct
3 Correct 2 ms 4728 KB Output is correct
4 Correct 0 ms 4728 KB Output is correct
5 Correct 0 ms 4728 KB Output is correct
6 Correct 1 ms 4728 KB Output is correct
7 Correct 0 ms 4728 KB Output is correct
8 Correct 0 ms 4728 KB Output is correct
9 Correct 0 ms 4728 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4992 KB Output is correct
2 Correct 39 ms 5784 KB Output is correct
3 Correct 14 ms 5256 KB Output is correct
4 Correct 23 ms 6268 KB Output is correct
5 Correct 29 ms 5388 KB Output is correct
6 Correct 42 ms 5784 KB Output is correct
7 Correct 21 ms 5784 KB Output is correct
8 Correct 30 ms 6268 KB Output is correct
9 Correct 28 ms 5920 KB Output is correct
10 Correct 21 ms 5784 KB Output is correct
11 Correct 27 ms 5652 KB Output is correct
12 Correct 18 ms 5388 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 6840 KB Output is correct
2 Correct 31 ms 5652 KB Output is correct
3 Correct 63 ms 6708 KB Output is correct
4 Correct 67 ms 6708 KB Output is correct
5 Correct 76 ms 6708 KB Output is correct
6 Correct 42 ms 6048 KB Output is correct
7 Correct 48 ms 6048 KB Output is correct
8 Correct 68 ms 6708 KB Output is correct
9 Correct 74 ms 6840 KB Output is correct
10 Correct 42 ms 5904 KB Output is correct
11 Correct 22 ms 5652 KB Output is correct
12 Correct 82 ms 6840 KB Output is correct
13 Correct 75 ms 6840 KB Output is correct
14 Correct 49 ms 6180 KB Output is correct
15 Correct 42 ms 5924 KB Output is correct
16 Correct 69 ms 6708 KB Output is correct
17 Correct 17 ms 5652 KB Output is correct