oj.uz

Submission #127093

# Submission time Handle Problem Language Result Execution time Memory
127093 2019-07-08T21:50:12 Z Mahmoud_Adel Mobile (BOI12_mobile) C++14
0 / 100
 762 ms 64344 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
const int N = 1e6+5;
int n, m;
pair<long double, long double> p[N];
stack<pair<int, pair<long double, long double>>> s;
long double dis(int i, long double x)
{
	long double y = 0;
	return hypot((x-p[i].f), (y-p[i].s));
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i=0; i<n; i++) cin >> p[i].f >> p[i].s;
	for(int i=0; i<n; i++)
	{
		if(s.empty()) s.push({i, {0, m}});
		else
		{
			auto t = s.top();
			if(p[i].f == p[t.f].f || dis(t.f, t.s.s) < dis(i, t.s.s)) 
			continue;
			long double x;
			while(!s.empty() && dis(s.top().f, s.top().s.f) >= dis(i, s.top().s.f)) x = s.top().s.f, s.pop();
			if(s.empty())
			{ 
				s.push({i, {0, m}});
				continue;
			}
			t = s.top();
			if(dis(t.f, t.s.s) >= dis(i, t.s.s))
			{
				long double l = t.s.f, r = t.s.s;
				for(int j=0; j<100; j++)
				{
					x = (l+r)/2;
					if(dis(t.f, x) <= dis(i, x)) l = x;
					else r = x;
				}
				/*
				long double x1 = p[i].f, x2 = p[t.f].f;
				long double y1 = p[i].s, y2 = p[t.f].s;
				x = (x1*x1 - x2*x2 + y1*y1-y2*y2)/(2*x1-2*x2);
				if(x <= t.s.f) continue;
				*/
				s.pop();
				t.s.s = x;
				s.push(t);
			}
			assert(dis(i, x)==dis(t.f, x));
			s.push({i, {x, m}});
		}
	}
	long double ans = 0;
	while(!s.empty())
	{
		auto t = s.top();
		s.pop();
		ans = max(ans, max(dis(t.f, t.s.f), dis(t.f, t.s.s)));
	}
	cout << fixed << setprecision(10) << ans << endl;
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:13:14: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return hypot((x-p[i].f), (y-p[i].s));
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:30:16: note: 'x' was declared here
    long double x;
                ^

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 5496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 5668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 6300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 78 ms 7056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 278 ms 32448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 382 ms 32264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 332 ms 38696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 455 ms 38708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 389 ms 45076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 532 ms 45128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 441 ms 51564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 610 ms 51472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 553 ms 64088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 762 ms 64344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -