Submission #592640

#	Time	Username	Problem	Language	Result	Execution time	Memory
592640		VasLemmy	Sure Bet (CEOI17_sure)	C++17	100 / 100	159 ms	14796 KiB

sure

/// slava sovet·skomu soyuzu
#include <bits/stdc++.h>
using namespace std;
using db = long double;
//#define int long long

#define ll long long
#define pdb pair<db,db>
#define fi first
#define se second
#define pb push_back

const ll mod = 1e9 + 7;
const int maxN = 5000005;

int n;
pdb a[maxN];
vector<pdb> bet2;
vector<pdb> bet1;
vector<pdb> subet2;
vector<pdb> subet1;

bool FA(pdb x,pdb y)
{
    return (x.fi > y.fi || (x.fi == y.fi && x.se > y.se));
}

void read()
{
    cout << fixed << setprecision(4);
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i].fi >> a[i].se;
        bet2.push_back({(db)-1,(db)(a[i].se-1)});
        bet1.push_back({(db)(a[i].fi-1),(db)-1});
    }
    sort(bet2.begin(),bet2.end(),FA);
    sort(bet1.begin(),bet1.end(),FA);
    /*for(pdb x : bet2)
    {
        cout << x.fi <<' '<< x.se <<'\n';
    }
    cout <<'*'<<'\n';
    for(pdb x : bet1)
    {
        cout << x.fi <<' '<< x.se <<'\n';
    }*/
    subet1.resize(bet1.size());
    for(int i = 0;i < bet1.size();i++)
    {
        if(i == 0) subet1[i] = bet1[i];
        else
        {
            subet1[i].fi = subet1[i-1].fi + bet1[i].fi;
            subet1[i].se = subet1[i-1].se + bet1[i].se;
        }
    }

    //cout <<"dark";return;
    pdb tmp = {0,0};
    db res = 0;
    for(int i = 0;i < bet2.size();i++)
    {
        tmp.fi += bet2[i].fi;
        tmp.se += bet2[i].se;
        int low = 0;
        int high = bet1.size() - 1;
        while(low <= high)
        {
            int mid = (low + high) / 2;
            if(tmp.fi + subet1[mid].fi <= tmp.se + subet1[mid].se)
            {
                low = mid + 1;
            }
            else high = mid - 1;
        }
        if(high >= 0 && high < bet1.size())
        {
            res = max(res,min(tmp.fi + subet1[high].fi,tmp.se + subet1[high].se));
        }
        if(low >= 0 && low < bet1.size())
        {
            res = max(res,min(tmp.fi + subet1[low].fi,tmp.se + subet1[low].se));
        }
        /*for(int j = 0;j < subet1.size();j++)
        {
            res = max(res,min(subet1[j].fi + tmp.fi,subet1[j].se + tmp.se));
            cout << i <<' '<< j <<' '<< res <<'\n';
        }*/
    }
    cout << res;
}

void sol()
{

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("test.inp","r",stdin);
    int tests;
    //cin >> tests;
    tests = 1;
    while (tests--)
    {
        read();
        sol();
    }
    return 0;
}

Compilation message (stderr)

sure.cpp: In function 'void read()':
sure.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0;i < bet1.size();i++)
      |                   ~~^~~~~~~~~~~~~
sure.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0;i < bet2.size();i++)
      |                   ~~^~~~~~~~~~~~~
sure.cpp:78:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         if(high >= 0 && high < bet1.size())
      |                         ~~~~~^~~~~~~~~~~~~
sure.cpp:82:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         if(low >= 0 && low < bet1.size())
      |                        ~~~~^~~~~~~~~~~~~

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