| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 807079 |
2023-08-04T13:01:50 Z |
NotLinux |
Seesaw (JOI22_seesaw) |
C++14 |
|
1 ms |
340 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});
}
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
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()){
| ~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
