oj.uz

Submission #608781

# Submission time Handle Problem Language Result Execution time Memory
608781 2022-07-27T10:04:25 Z kshitij_sodani Seesaw (JOI22_seesaw) C++14
100 / 100
 634 ms 30436 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
1.0 / 1.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 4 ms 648 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 624 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 4 ms 648 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 624 KB Output is correct
12 Correct 634 ms 30312 KB Output is correct
13 Correct 596 ms 30436 KB Output is correct
14 Correct 565 ms 30412 KB Output is correct
15 Correct 600 ms 30324 KB Output is correct
16 Correct 492 ms 30424 KB Output is correct