| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 807070 |
2023-08-04T12:58:37 Z |
NotLinux |
Seesaw (JOI22_seesaw) |
C++17 |
|
0 ms |
0 KB |
#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});
}
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;
auto cmp = [](pair < int , int > a , pair < int , int > b){return (a.first * b.second) < (a.second * b.first);};
multiset < pair < int , int > , decltype(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
seesaw.cpp: In function 'void solve()':
seesaw.cpp:35:23: warning: variable 'cand2' set but not used [-Wunused-but-set-variable]
35 | pair < int , int > cand2 = {sum - arr[rp] , m};
| ^~~~~
seesaw.cpp:43:23: warning: variable 'cand1' set but not used [-Wunused-but-set-variable]
43 | pair < int , int > cand1 = {sum - arr[lp] , m};
| ^~~~~
seesaw.cpp:89: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]
89 | while(rp < possible.size()){
| ~~~^~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/map:60,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
from seesaw.cpp:1:
/usr/include/c++/10/bits/stl_tree.h: In instantiation of 'std::_Rb_tree_key_compare<_Key_compare>::_Rb_tree_key_compare() [with _Key_compare = solve()::<lambda(std::pair<long long int, long long int>, std::pair<long long int, long long int>)>]':
/usr/include/c++/10/bits/stl_tree.h:688:22: required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Rb_tree_impl<_Key_compare, <anonymous> >::_Rb_tree_impl() [with _Key_compare = solve()::<lambda(std::pair<long long int, long long int>, std::pair<long long int, long long int>)>; bool <anonymous> = false; _Key = std::pair<long long int, long long int>; _Val = std::pair<long long int, long long int>; _KeyOfValue = std::_Identity<std::pair<long long int, long long int> >; _Compare = solve()::<lambda(std::pair<long long int, long long int>, std::pair<long long int, long long int>)>; _Alloc = std::allocator<std::pair<long long int, long long int> >]'
/usr/include/c++/10/bits/stl_tree.h:935:7: required from here
/usr/include/c++/10/bits/stl_tree.h:149:24: error: use of deleted function 'solve()::<lambda(std::pair<long long int, long long int>, std::pair<long long int, long long int>)>::<lambda>()'
149 | : _M_key_compare()
| ^
seesaw.cpp:56:14: note: a lambda closure type has a deleted default constructor
56 | auto cmp = [](pair < int , int > a , pair < int , int > b){return (a.first * b.second) < (a.second * b.first);};
| ^
