Submission #1079081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079081		prvocislo	Seesaw (JOI22_seesaw)	C++17	100 / 100	108 ms	30696 KiB

seesaw

// I was grinning like I'm winning, I was hitting my marks
// 'Cause I can do it with a broken heart 
// 1 2 3 4 ...
 
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <bitset>
typedef long long ll;
typedef long double ld;
using namespace std;
 
vector<ll> a, pf;
 
ld avg(int l, int r) { return (ld)(pf[r + 1] - pf[l]) / (ld)(r - l + 1); }
 
void chmax(ld& a, ld b) { a = max(a, b); }
void chmin(ld& a, ld b) { a = min(a, b); }
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	a.assign(n, 0), pf.assign(n + 1, 0);
	for (int i = 0; i < n; i++) cin >> a[i], pf[i + 1] = pf[i] + a[i];
	ld w = avg(0, n - 1);
	vector<pair<ld, int>> v;
	v.push_back({ avg(0, n - 1), n });
	v.push_back({ avg(0, n - 2), n - 1 });
	v.push_back({ avg(1, n - 1), n - 1 });
	int l = 0;
	for (int i = n - 2; i >= 1; i--)
	{
		if (avg(l + 1, l + i) <= w) l++;
		v.push_back({ avg(l, l + i - 1), i });
		v.push_back({ avg(l + 1, l + i), i });
	}
	ld ans = w;
	stable_sort(v.begin(), v.end());
	vector<int> f(n + 1, 0);
	int cnt = 0, r = 0;
	for (int l = 0; l < v.size(); l++)
	{
		while (cnt < n && r < v.size())
		{
			if (!f[v[r].second]) cnt++;
			f[v[r].second]++;
			r++;
		}
		if (cnt == n) ans = min(ans, v[r - 1].first - v[l].first);
		f[v[l].second]--;
		if (!f[v[l].second]) cnt--;
	}
	cout << setprecision(9) << fixed;
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int l = 0; l < v.size(); l++)
      |                  ~~^~~~~~~~~~
seesaw.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   while (cnt < n && r < v.size())
      |                     ~~^~~~~~~~~~

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