Submission #1243432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243432		sinatbtfard	Measures (CEOI22_measures)	C++20	10 / 100	1598 ms	5144 KiB

Main

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn = 2e5 + 10;

int n, q, d;
vector <double> v;

void read (){
	cin >> n >> q >> d;
	for (int x, i = 0; i < n; i++){
		cin >> x;
		v.push_back(x);
	}
}

bool check (vector <double> a, double x){
	int m = a.size();
	a[0] -= x;
	for (int i = 1; i < m; i++){
		if (a[i - 1] + d > a[i] + x) return 0;
		a[i] = max(a[i - 1] + d, a[i] - x);
	}
	return 1;
}

const double zt[10] = {0.1, 0.01, 0.001, 0.0001, 0.00001, 0.000001, 0.0000001, 0.00000001, 0.000000001, 0.0000000001};

pair <double, int> get (vector <double> v){
	double res = 0;
	int l = 0, r = 1e15;
	while (r - l > 1){
		int mid = (r + l) >> 1;
		(check(v, mid) ? r : l) = mid;
	}
	int cnt = 0;
	res += l;
	for (int i = 0; i < 10; i++){
		int l = 0, r = 10;
		while (r - l > 1){
			int mid = (r + l) >> 1;
			(check(v, res + mid * zt[i]) ? r : l) = mid;
		}
		if (r == 1 || r == 10){
			if (r == 10) res += 10 * zt[i];
			break;
		}
		res += l * zt[i];
		cnt++;
	}
	return {res, cnt};
}

void solve (){
	for (int x, qq = 0; qq < q; qq++){
		cin >> x;
		v.push_back(x);
		sort(v.begin(), v.end());
		auto [ans, cnt] = get(v);
		cout << fixed << setprecision(cnt) << ans << '\n';
	}
}

int32_t main (){
	ios_base::sync_with_stdio(0), cin.tie(0);
	read();
	solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41