Submission #678287

#	Time	Username	Problem	Language	Result	Execution time	Memory
678287		arnold518	Seesaw (JOI22_seesaw)	C++17	100 / 100	149 ms	9612 KiB

seesaw

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int N, A[MAXN+10];
ll S[MAXN+10];

bool cmp(pii p, pii q)
{
	p.first--; q.first--;
	return (__int128)(S[p.second]-S[p.first])*(q.second-q.first) < (__int128)(S[q.second]-S[q.first])*(p.second-p.first);
}

pii mmin(pii p, pii q)
{
	if(cmp(p, q)) return p;
	else return q;
}

pii mmax(pii p, pii q)
{
	if(cmp(p, q)) return q;
	return p;
}

pii B[MAXN+10], C[MAXN+10];
int T[MAXN+10];

double ans=1e18;

double avg(pii x)
{
	x.first--;
	return (double)(S[x.second]-S[x.first])/(x.second-x.first);
}

void f(pii l, pii r)
{
	//printf("%d %d / %d %d\n", l.first, l.second, r.first, r.second);
	ans=min(ans, avg(r)-avg(l));
}

struct CMP
{
	bool operator () (const pair<pii, int> &p, const pair<pii, int> &q) const
	{
		return !cmp(p.first, q.first);
	}
};

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]), S[i]=S[i-1]+A[i];

	for(int i=1; i<=N; i++)
	{
		int lo=0, hi=N-i+2;
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(cmp(pii(mid, mid+i-1), pii(1, N))) lo=mid;
			else hi=mid;
		}
		B[i]=pii(lo, lo+i-1);
		C[i]=pii(hi, hi+i-1);
	}

	pii l(1, N), r(1, N);

	priority_queue<pair<pii, int>, vector<pair<pii, int>>, CMP> PQ;
	for(int i=1; i<=N; i++)
	{
		if(1<=B[i].first && C[i].second<=N) PQ.push({B[i], i}), r=mmax(r, B[i]);
		else if(1<=B[i].first) l=mmin(l, B[i]), r=mmax(r, B[i]);
		else l=mmin(l, C[i]), r=mmax(r, C[i]);
	}

	while(!PQ.empty())
	{
		auto t=PQ.top(); PQ.pop();
		f(mmin(l, t.first), r);
		//printf("WOW %d %d\n", t.first.first, t.first.second);
		r=mmax(r, C[t.second]);
		l=mmin(l, C[t.second]);
	}
	f(l, r);

	printf("%.10lf\n", ans);
}

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:66:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |    int mid=lo+hi>>1;
      |            ~~^~~
seesaw.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
seesaw.cpp:59:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]), S[i]=S[i-1]+A[i];
      |                          ~~~~~^~~~~~~~~~~~~

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