oj.uz

Submission #608777

# Submission time Handle Problem Language Result Execution time Memory
608777 2022-07-27T10:03:33 Z kshitij_sodani Seesaw (JOI22_seesaw) C++14
0 / 100
 1 ms 328 KB 
#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

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
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 328 KB Output isn't correct
3 Halted 0 ms 0 KB -