Submission #878004

#	Time	Username	Problem	Language	Result	Execution time	Memory
878004		phong	Sure Bet (CEOI17_sure)	C++17	100 / 100	229 ms	2132 KiB

sure

#include <bits/stdc++.h>


using ll = long long;
const int nmax = 1e5 + 5;
const int lg = 20;
const int mod = 1e9 + 7;
const ll oo = 1e18;
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;

int n, q, t;

double a[nmax], b[nmax];

bool check(double k){
    for(int i = 0; i <= n; ++i){
        int l = 0, r = n, it1 = -1;
        while(l <= r){
            int mid = r + l >> 1;
            if(a[i] - i - mid >= k){
                it1 = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        if(it1 != -1){
            if(a[i] - i - it1 >= k && b[it1] - it1 - i >= k) return 1;
        }
    }
    return 0;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
    sort(a + 1, a + 1 + n, greater<double> ());
    sort(b + 1, b + 1 + n, greater<double> ());
    for(int i = 1; i <= n; ++i){
        a[i] += a[i - 1];
        b[i] += b[i - 1];
    }
    double l = 0, r = 2e8, kq = 0;
    for(int t = 1; t <= 50; ++t){
        double mid = (r + l) / 2;
        if(check(mid)){
            kq = mid;
            l = mid;
        }
        else r = mid;
    }
    cout << fixed << setprecision(4) << kq;
}
/*
10
4.0530 1.2670
4.3790 2.1420
1.9230 2.1920
3.3740 1.0850
0.9690 3.4510
1.5270 0.5160
4.3860 1.3360
4.5560 1.5050
4.9650 1.8120
0.6250 0.4820

*/

Compilation message (stderr)

sure.cpp: In function 'bool check(double)':
sure.cpp:22:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |             int mid = r + l >> 1;
      |                       ~~^~~

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