Submission #1077742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077742		prvocislo	Seesaw (JOI22_seesaw)	C++17	100 / 100	108 ms	22212 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;
	for (int i = 1; i <= n; i++)
	{
		int l = 0, r = n - i;
		while (l < r)
		{
			int m = (l + r + 1) / 2;
			if (avg(m, m + i - 1) <= w) l = m;
			else r = m - 1;
		}
		v.push_back({ avg(l, l + i - 1), i });
		if (l + i < n) v.push_back({ avg(l + 1, l + i), i });
	}
	ld ans = w;
	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:50: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]
   50 |  for (int l = 0; l < v.size(); l++)
      |                  ~~^~~~~~~~~~
seesaw.cpp:52: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]
   52 |   while (cnt < n && r < v.size())
      |                     ~~^~~~~~~~~~

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