oj.uz

Submission #974274

# Submission time Handle Problem Language Result Execution time Memory
974274 2024-05-03T07:14:29 Z happy_node Seesaw (JOI22_seesaw) C++17
100 / 100
 216 ms 33596 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int MX=2e5+5;

int N;
ll A[MX];

ld f(int l, int r) {
	return (ld)(A[r]-A[l-1])/(r-l+1);
}

vector<pair<ld,int>> v;

ld L[MX], R[MX];
int idL[MX], idR[MX];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N;
	for(int i=1;i<=N;i++) {
		cin>>A[i];
		A[i]+=A[i-1];
	}

	for(int k=1;k<=N;k++) {
		int l=k,r=N,res=0;
		while(l<=r) {
			int mid=(l+r)/2;
			if(f(mid-k+1,mid)>=f(1,N)) {
				res=mid,r=mid-1;
			} else {
				l=mid+1;
			}
		}
		// f(res-k,res-1) or f(res-k+1,res)
		if(res-k<1)
			L[k]=f(res-k+1,res);
		else
			L[k]=f(res-k,res-1);
		R[k]=f(res-k+1,res);

		v.push_back({L[k],k});
		v.push_back({R[k],k});
	}

	sort(v.begin(),v.end());

	int id=1;
	for(auto [x,k]:v) {
		if(!idL[k]) idL[k]=id;
		else idR[k]=id;
		id++;
	}

	/* 

	each k adds 2 important point f(l,l+k-1) or f(l+1,l+k) 
	for some l s.t. f(l,l+k-1) <= f(1,N) <= f(l+1,l+k)

	a range [L,R] is valid iff every k in [1,N] exist atleast one important point

	we can show sufficiency by noticing that 

	(*) f(l,r) < f(l+1,r+1) < f(l+2,r+2) < ... 

	also notice that important points are two consecutive terms in (*)
	
	now plot each f(l,r) in a similar fashion to pascal's triangle 
	where each row groups all ranges with same length

	assume we reach the k-th row and want to go down to (k+1) th row
		
	if we're in the left imp. point of k-th row which is in [L,R]
	
	the option is to either go to the left imp. point of (k+1)-th row of right imp. point

	if left imp. point is in [L,R] we are done

	if left imp. point isn't in [L,R] then it must either be in [1,L) or (R,N]

	if it is in (R,N], this is absurd due to our assumption that there exist an imp point of range
	(k+1) in [L,R]
	
	if it is in [1,L), then the right imp. point must be in [L,R] so we can go there and we are done.
	
	this is because since we are in left imp. point of k-th row
	it can produce to imp. point in k+1 th row
	also notice that f(l,r-1) < f(l,r) < f(l+1,r) 
	so what it produces is one is to its left and one is to its right
	since one is already to its left, the other one must be to its right
	
	*/

	set<int> st;
	for(int k=1;k<=N;k++) st.insert(idL[k]);
	
	ld ans=2e18;
	for(auto [x,k]:v) {
		int res=0;
		if(st.size()==N) res=*st.rbegin();

		if(res!=0) {
			ans=min(ans,v[res-1].first-x);
		}
		if(idL[k]) {
			st.erase(idL[k]);
			st.insert(idR[k]);
			idL[k]=0;
		} else {
			st.erase(idR[k]);
		}
	}

	cout<<fixed<<setprecision(10)<<ans<<'\n';

}

Compilation message

seesaw.cpp: In function 'int main()':
seesaw.cpp:104:15: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |   if(st.size()==N) res=*st.rbegin();
      |      ~~~~~~~~~^~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6616 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6616 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6608 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6616 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6608 KB Output is correct
8 Correct 2 ms 7000 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 3 ms 6744 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6616 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6608 KB Output is correct
8 Correct 2 ms 7000 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 3 ms 6744 KB Output is correct
12 Correct 186 ms 31916 KB Output is correct
13 Correct 171 ms 31916 KB Output is correct
14 Correct 216 ms 31604 KB Output is correct
15 Correct 173 ms 32576 KB Output is correct
16 Correct 172 ms 33596 KB Output is correct