Submission #807079

#	Time	Username	Problem	Language	Result	Execution time	Memory
807079		NotLinux	Seesaw (JOI22_seesaw)	C++14	0 / 100	1 ms	340 KiB

seesaw

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 7;
int n , arr[N] , pre[N];
bool smoll(pair < int , int > a , pair < int , int > b){
	return (a.first * b.second) < (a.second * b.first);
}
pair < int , int > simp(pair < int , int > a){
	return {a.first / __gcd(a.first,a.second) , a.second / __gcd(a.first,a.second)};
}
pair < int , int > MAX(pair < int , int > a , pair < int , int > b){
	if(smoll(a,b))return b;
	return a;
}
pair < int , int > MIN(pair < int , int > a , pair < int , int > b){
	if(smoll(a,b))return a;
	return b;
}
pair < int , int > SUB(pair < int , int > a , pair < int , int > b){
	return simp({a.first * b.second - a.second * b.first , a.second * b.second});
}
struct cmp{
	bool operator() (pair < int , int > a , pair < int , int > b) const {
		return (a.first * b.second) < (a.second * b.first);
	}
};
void solve(){
	cin >> n;
	for(int i = 0;i<n;i++){
		cin >> arr[i];
		pre[i+1] = pre[i] + arr[i];
	}
	vector < pair < int , int > > cur = {{0,n-1}}, endp = {{0,n-1}};
	const pair < int , int > barycenter = {pre[n] , n};

		int lp = 0 , rp = n-1 , sum = pre[n];
		for(int m=n-1;m>0;m--){
			pair < int , int > cand1 = {sum - arr[lp] , m};
			pair < int , int > cand2 = {sum - arr[rp] , m};
			if(smoll(cand1 , barycenter))sum -= arr[lp++];
			else sum -= arr[rp--];
			cur.push_back({lp,rp});
		}

		lp = 0 , rp = n-1 , sum = pre[n];
		for(int m=n-1;m>0;m--){
			pair < int , int > cand1 = {sum - arr[lp] , m};
			pair < int , int > cand2 = {sum - arr[rp] , m};
			if(smoll(barycenter , cand2))sum -= arr[rp--];
			else sum -= arr[lp++];
			endp.push_back({lp,rp});
		}

	function < pair < int , int > (pair < int , int >) > eval = [&](pair < int , int > a){
		return simp({pre[a.second+1] - pre[a.first] , a.second - a.first + 1});
	};

	map < pair < int , int > , vector < int > > IND;
	map < pair < int , int > , vector < pair < int , int > > >  VAL;
	multiset < pair < int , int > , cmp > ste;
	for(auto itr : cur){ste.insert(eval(itr));VAL[eval(itr)].push_back(itr);}
	for(auto itr : endp){ste.insert(eval(itr));VAL[eval(itr)].push_back(itr);}
	for(auto &itr : VAL){
		sort(itr.second.begin() , itr.second.end());
		itr.second.resize(unique(itr.second.begin(),itr.second.end()) - itr.second.begin());
	}
	vector < pair < int , int > > possible;
	for(auto itr : ste)if(possible.size() == 0 or possible.back() != itr)possible.push_back(itr);
	for(auto itr : endp)ste.erase(ste.find(eval(itr)));
	for(int i = 0;i<(int)cur.size();i++)IND[eval(cur[i])].push_back(i);
	pair < int , int > mn = {1e9 + 7,1} , mx = {0,1};
	
	for(int i = 0;i<(int)cur.size();i++){
		mn = MIN(mn , eval(cur[i]));
		mx = MAX(mx , eval(cur[i]));
	}
	/*cout << "possible : ";for(auto itr : possible)cout << itr.first << "/" << itr.second << "   ";cout << endl;
	cout << "cur : ";for(auto itr : cur)cout << itr.first << "/" << itr.second << "   ";cout << endl;
	cout << "endp : ";for(auto itr : endp)cout << itr.first << "/" << itr.second << "   ";cout << endl;
	cout << "ste : ";for(auto itr : ste)cout << itr.first << "/" << itr.second << "   ";cout << endl;*/
	lp = 0 , rp = 0;
	while(possible[lp] != mn)lp++;
	while(possible[rp] != mx)rp++;
	pair < int , int > ans = {1e9 + 7,1};
	set < pair < int , int > > forbidden , exist;
	for(auto itr : endp)forbidden.insert(itr);
	for(auto itr : cur){exist.insert(itr);}
	ans = MIN(ans , SUB(*(--ste.end()) , *ste.begin()));
	/*cout << "local ans : " << SUB(*(--ste.end()) , *ste.begin()).first << "/" << SUB(*(--ste.end()) , *ste.begin()).second << endl;
	cout << "curmin =>" << (*(ste.begin())).first << "/" << (*(ste.begin())).second << endl;
	cout << "curmax =>" << (*(--ste.end())).first << "/" << (*(--ste.end())).second << endl;*/
	while(rp < possible.size()){
		bool fail = 0 , abort = 0;
		//tüm L lere bak siblingi olmayan varsa R yi arttırman gerek 
		//cout << "\n\nlp : " << lp << " - rp : " << rp << endl;
		for(auto itr : IND[possible[lp]]){
			//cout << "should be shifted : " << cur[itr].first << "-" << cur[itr].second << endl;
			if(forbidden.count(cur[itr])){abort = 1;}
			if(exist.count({cur[itr].first+1,cur[itr].second+1}) == 0){fail = 1;}
		}
		//cout << "fail : " << fail << " - abort : " << abort << endl;
		if(fail or abort){
			if(abort)break;
			for(auto itr : VAL[possible[rp]]){
		//		cout << "added : " << itr.first << "-" << itr.second << endl;
				exist.insert(itr);
			}
			rp++;
		}
		else{
			for(auto itr : IND[possible[lp]]){
		//		cout << "change : " << cur[itr].first << "-" << cur[itr].second << endl;
				ste.erase(ste.find(eval(cur[itr])));
				cur[itr] = {cur[itr].first + 1 , cur[itr].second + 1};
				ste.insert(eval(cur[itr]));
				IND[eval(cur[itr])].push_back(itr);
			}
			IND[possible[lp]].clear();
			lp++;
		}
		/*cout << "cur : ";for(auto itr : cur)cout << itr.first << "/" << itr.second << "   ";cout << endl;
		cout << "local ans : " << SUB(*(--ste.end()) , *ste.begin()).first << "/" << SUB(*(--ste.end()) , *ste.begin()).second << endl;
		cout << "exist : ";for(auto itr : exist)cout << itr.first << "-" << itr.second << "   ";cout << endl;*/
		ans = MIN(ans , SUB(*(--ste.end()) , *ste.begin()));
	}
	cout << setprecision(9) << (double)ans.first / (double)ans.second << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}
/*
 - dont loop over same ideas
 - abandon the problem if you have no idea
 - think about implementation
*/

Compilation message (stderr)

seesaw.cpp: In function 'void solve()':
seesaw.cpp:40:23: warning: variable 'cand2' set but not used [-Wunused-but-set-variable]
   40 |    pair < int , int > cand2 = {sum - arr[rp] , m};
      |                       ^~~~~
seesaw.cpp:48:23: warning: variable 'cand1' set but not used [-Wunused-but-set-variable]
   48 |    pair < int , int > cand1 = {sum - arr[lp] , m};
      |                       ^~~~~
seesaw.cpp:93:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  while(rp < possible.size()){
      |        ~~~^~~~~~~~~~~~~~~~~

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