Submission #877990

#	Time	Username	Problem	Language	Result	Execution time	Memory
877990		phong	Sure Bet (CEOI17_sure)	C++17	0 / 100	0 ms	2396 KiB

sure

#include <bits/stdc++.h>

#define int long long

using ll = long long;
const int nmax = 1e6 + 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, it2 = -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 && double(b[it1] - it1 - i) >= k) return 1;
        }
    }
    return 0;
}
 main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    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 = -1;
    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;
}
/*
ai
*/

Compilation message (stderr)

sure.cpp: In function 'bool check(double)':
sure.cpp:23:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |             int mid = r + l >> 1;
      |                       ~~^~~
sure.cpp:21:37: warning: unused variable 'it2' [-Wunused-variable]
   21 |         int l = 0, r = n, it1 = -1, it2 = -1;
      |                                     ^~~
sure.cpp: At global scope:
sure.cpp:37:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 |  main(){
      |  ^~~~

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