Submission #1027252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027252		idkman	Sure Bet (CEOI17_sure)	C++14	100 / 100	63 ms	3568 KiB

sure

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll  i=(a);i<=(b);i++)
#define Ford(i,a,b) for(ll  i=(a);i>=(b);i--)
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define endl "\n"
using namespace std;
int Dx[] = {0, 1, 0, -1, -1, -1, 1, 1};
int Dy[] = {-1, 0, 1, 0, 1, -1, 1, -1};
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
const ll inf = 1000000000000000000;
const int N = 100000;
const int block_size = 300;
const ll MOD =  1e9 + 7; /* 998244353 */
const int LG = 18;
const int K = 20;	
const int M = 10000000;
ll nph(ll k, ll x) { return ((x >> k) & 1LL); }
#define ld double
ll n;
ld a[N+3],b[N+3], prea[N+3], preb[N+3];
bool cmp(ld a, ld b) {
	return a > b;
}
ld f(ll x, ll y) {
	return min(prea[x] - 1.0 * y, preb[y] - 1.0 * x);
}
ld binsech(ll x) {
	ll l = 1, r = n, ans = -1;
	if(n == 1) return f(x, 1);
	if(n == 2) return max(f(x, 1), f(x, 2));
	while(l <= r) {
		ll md = l + r >> 1;
		ll s = md - 1, t = md, u = md + 1;
		if(s == 0) {
			ans = t; l = md + 1;
			continue;
		}
		if(u == n+1) {
			ans = t; r = md - 1;
		}
		if(f(x, s) <= f(x, t) && f(x, t) <= f(x, u)) {
			ans = u; l = md + 1;
		}
		else if(f(x, s) >= f(x, t) && f(x, t) >= f(x, u)) {
			ans = s; r = md - 1;
		}
		else if(f(x, s) <= f(x, t) && f(x, t) >= f(x, u)) {
			return f(x, t);
		}
	}
	return f(x, ans);
}
void Solve() { 
	cin>>n;
	ld ans = 0.0;
	For(i, 1, n) cin>>a[i]>>b[i];
	For(i, 1, n) {a[i]--; b[i]--;}
	sort(a+1, a+n+1, cmp); sort(b+1, b+n+1, cmp);
	For(i, 1, n) prea[i] = prea[i-1] + a[i];
	For(i, 1, n) preb[i] = preb[i-1] + b[i];
	For(i, 1, n) {
		ans = max(ans, binsech(i));
	}
	cout << fixed << setprecision(4) << ans;
}	

int main() {
    // freopen("AVGSEQ.INP", "r", stdin);
    // freopen("AVGSEQ.OUT", "w", stdout);
    ios_base::sync_with_stdio(0); 
    cin.tie(NULL); 
    cout.tie(NULL);
    int t = 1;
    //cin >> t; 
    while(t--) 
    	Solve();
}

Compilation message (stderr)

sure.cpp: In function 'double binsech(long long int)':
sure.cpp:39:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |   ll md = l + r >> 1;
      |           ~~^~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40