Submission #801952

#	Time	Username	Problem	Language	Result	Execution time	Memory
801952		ymm	Seesaw (JOI22_seesaw)	C++17	100 / 100	45 ms	8012 KiB

seesaw

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
using namespace std;

const int N = 200'010;
double pos[N];
double sum;
int n;

vector<pair<double,double>> arr;
void make()
{
	double sum = ::sum;
	double m = sum/n;
	int p0 = 0, p1 = n-1;
	pos[n] = 2e9;
	auto cur_pair = [&]() {
		return pair<double,double>(sum/(p1-p0+1), (sum - pos[p0] + pos[p1+1])/(p1-p0+1));
	};
	arr = {cur_pair()};
	for (int cnt = n; p0 < p1; --cnt) {
		if ((sum-pos[p0])/(cnt-1) <= m) {
			sum -= pos[p0];
			++p0;
		} else {
			sum -= pos[p1];
			--p1;
		}
		arr.push_back(cur_pair());
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n) {
		ll x;
		cin >> x;
		pos[i] = x;
		sum += pos[i];
	}
	make();
	sort(arr.begin(), arr.end(), [](const pair<double,double> &a, const pair<double,double> &b){
		return a.second < b.second;
	});
	LoopR (i,0,arr.size()-1)
		arr[i].first = min(arr[i].first, arr[i+1].first);
	double m = sum/n;
	double ans = min(m - arr.front().first, arr.back().second - m);
	Loop (i,0,arr.size()-1)
		ans = min(ans, arr[i].second - arr[i+1].first);
	cout << fixed << setprecision(9);
	cout << ans << '\n';
}

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<double, double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
seesaw.cpp:53:2: note: in expansion of macro 'Loop'
   53 |  Loop (i,0,arr.size()-1)
      |  ^~~~

• Subtask 1: 1 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33