oj.uz

Submission #908430

# Submission time Handle Problem Language Result Execution time Memory
908430 2024-01-16T12:07:33 Z roimu Balloons (CEOI11_bal) C++14
0 / 100
 500 ms 11380 KB 
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>
#include <assert.h>

using namespace std;

typedef long long LL;
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

bool f(pair<long double, long double> a, pair<long double, long double> b) {

	long double bound = a.first;
	long double two = 2.000000000000000;
	bound += a.second * two;
	return b.first >= bound;
}

long double dist(pair<long double, long double> a, pair<long double, long double> b) {
	long double four = 4.0000000000000000;
	return (a.first - b.first)*(a.first - b.first) / four*a.second;
}

int main() {
	int n; cin >> n;
	vector<pair<long double, long double>> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}

	vector<long double> ans(n);
	ans[0] = a[0].second;
	stack<pair<long double, long double>> st;
	st.push(a[0]);
	for (int i = 1; i < n; i++) {
		long double rnow = 100000000000.0;
		//小さいうちは潰し続ける、潰したときの半径を覚えておく
		while (!st.empty() and f(st.top(),a[i])) {
			rnow = min(rnow, dist(st.top(), a[i]));
			st.pop();
		}

		if (!st.empty()) {
			rnow = min(rnow, dist(st.top(), a[i]));
		}
		rnow = min(rnow, a[i].second);
		ans[i] = rnow;
		st.push({ a[i].first,rnow });
	}

	for (int i = 0; i < n; i++) {
		cout << fixed << setprecision(3) << ans[i] << endl;
	}

	return 0;
}

/*
2
0 2
20 10

*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB 2nd numbers differ - expected: '4.1670000000', found: '7.0000000000', error = '2.8330000000'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB 2nd numbers differ - expected: '252735385.4379999936', found: '1000000000.0000000000', error = '747264614.5620000362'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 496 KB 2nd numbers differ - expected: '0.0010000000', found: '3.0000000000', error = '2.9990000000'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 348 KB 2nd numbers differ - expected: '122.0020000000', found: '123.0000000000', error = '0.9980000000'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 1368 KB 2nd numbers differ - expected: '212.0010000000', found: '213.0000000000', error = '0.9990000000'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 3156 KB 2nd numbers differ - expected: '15398.0000000000', found: '24984.0000000000', error = '9586.0000000000'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 250 ms 5976 KB 2nd numbers differ - expected: '7937.0000000000', found: '10352.0000000000', error = '2415.0000000000'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 294 ms 6736 KB 2nd numbers differ - expected: '5059.0000000000', found: '5060.0000000000', error = '1.0000000000'
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 368 ms 8908 KB 2nd numbers differ - expected: '1873.0000000000', found: '1874.0000000000', error = '1.0000000000'
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 500 ms 11380 KB 2nd numbers differ - expected: '2961.0000000000', found: '2962.0000000000', error = '1.0000000000'
2 Halted 0 ms 0 KB -