oj.uz

Submission #683998

# Submission time Handle Problem Language Result Execution time Memory
683998 2023-01-19T23:18:20 Z as111 Mobile (BOI12_mobile) C++14
0 / 100
 622 ms 48148 KB 
#include <bits/stdc++.h>
#define ll long long
#define MAXN 1000000
using namespace std;
int N, L;
vector<pair<ll, ll>> stns;
ll lt[MAXN + 5]; // point to the left
ll frac[MAXN + 5][2]; // point hypotenuse equals to station to the left, num and den
ll reach[MAXN + 5][2];
bool comp(int a, int b) {
	ll ax = stns[a].first;
	ll bx = stns[b].first;
	if (frac[b][0] * frac[a][1] > frac[b][1] * (frac[a][0]+(bx-ax)*frac[a][1])) { // right point reaches further to the left than left does, delete left
		return true;
	}
}
void dist(int a, int b) {
	ll ax = stns[a].first;
	ll ay = stns[a].second;
	ll bx = stns[b].first;
	ll by = stns[b].second;
	frac[b][0] = (ay * ay) + (bx - ax) * (bx - ax) - (by * by);
	frac[b][1] = 2 * (bx - ax);
	if (bx * frac[b][1] < frac[b][0]) frac[b][0] = 0; // point reaches to the left of 0, reset to 0
}
int main() {
	cin >> N >> L;
	stns.push_back({ -2000000001, -1000000001 });
	for (int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		if (stns.back().first == x) { // another with same x value
			if (abs(stns.back().first) < abs(x)) continue;
			else { // this one is closer, remove other of same x value
				stns.pop_back();
				stns.push_back({ x, y });
			}
		}
		else {
			stns.push_back({ x, y });
		}
	}
	for (int i = 1; i <= N; i++) {
		dist(i-1, i);
	}
	lt[1] = -1;
	for (int i = 2; i <= N; i++) {
		int prev = i - 1;
		while (prev != -1) {
			if (comp(i, prev)) {
				prev = lt[prev];
			}
			else {
				lt[i] = prev;
				break;
			}
		}
		if (prev == -1) lt[i] = -1; // leftmost point
	}
	double ans = 0;
	for (int i = N; i >= 1; i = lt[i]) {
		double hyp = sqrt(pow((double)frac[i][0] / (double)frac[i][1], 2) + pow(stns[i].second, 2));
		ans = max(ans, hyp);
	}
	cout << ans;
}

Compilation message

mobile.cpp: In function 'bool comp(int, int)':
mobile.cpp:16:1: warning: control reaches end of non-void function [-Wreturn-type]
   16 | }
      | ^

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 4048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 1808 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 4508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 72 ms 5616 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 5852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 237 ms 24320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 327 ms 9668 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 29080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 394 ms 11032 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 303 ms 33848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 432 ms 12548 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 354 ms 38784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 506 ms 14252 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 423 ms 48148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 622 ms 17548 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -