Submission #608781

#	Time	Username	Problem	Language	Result	Execution time	Memory
608781		kshitij_sodani	Seesaw (JOI22_seesaw)	C++14	100 / 100	634 ms	30436 KiB

seesaw

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'
#include <iostream>

llo it[200001];
llo pre[200001];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n;
	
	cin>>n;
	
	for(llo i=0;i<n;i++){
		cin>>it[i];
		pre[i+1]=pre[i]+it[i];
	}
	long double ss2=(long double)pre[n]/(long double)n;
	vector<pair<long double,llo>> ss;
	ss.pb({ss2,n-1});
	for(llo i=n-2;i>=0;i--){
		llo low=0;
		for(llo j=19;j>=0;j--){
			if(low+(1<<j)+i<n){
				long double tt=(long double)(pre[low+(1<<j)+i+1]-pre[low+(1<<j)]);
				tt/=(long double)(i+1);
				if(tt<=ss2-0.0000000000001){
					low+=(1<<j);
				}
			}
		}

		long double tt=(long double)(pre[low+i+1]-pre[low]);
		tt/=(long double)(i+1);
		ss.pb({tt,i});
		low++;

		tt=(long double)(pre[low+i+1]-pre[low]);
		tt/=(long double)(i+1);
		ss.pb({tt,i});
	}

	sort(ss.begin(),ss.end());
	map<llo,llo> tt;
	llo su=0;
	llo ind=0;
	for(llo i=0;i<n;i++){
		tt[i]=0;
	}
	long double ans=10000000000;
	for(llo i=0;i<ss.size();i++){
		
		if(tt[ss[i].b]==0){
			su++;
			tt[ss[i].b]++;
		}
		else{
			tt[ss[i].b]++;
		}
		if(su==n){
			while(ind<i){
				if(tt[ss[ind].b]>1){
					tt[ss[ind].b]--;
					ind++;
				}
				else{
					break;
				}
			}
		}
		if(su==n){
			if(ss[i].a-ss[ind].a<ans-0.0000000000001){
				ans=ss[i].a-ss[ind].a;
			}
		}
	}

		cout<<setprecision(10)<<ans<<endl;

	return 0;
}

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:57:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long double, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(llo i=0;i<ss.size();i++){
      |              ~^~~~~~~~~~

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