oj.uz

Submission #592607

# Submission time Handle Problem Language Result Execution time Memory
592607 2022-07-09T10:52:52 Z VasLemmy Sure Bet (CEOI17_sure) C++17
0 / 100
 0 ms 212 KB 
/// slava sovet·skomu soyuzu
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define db double
#define ll long long
#define pdb pair<double,double>
#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 = -1;
    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,tmp.fi + subet1[high].fi);
        }
        else if(low >= 0 && low < bet1.size())
        {
            res = max(res,tmp.se + subet1[low].se);
        }
    }
    cout << res;
}

void sol()
{

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tests;
    //cin >> tests;
    tests = 1;
    while (tests--)
    {
        read();
        sol();
    }
    return 0;
}

Compilation message

sure.cpp: In function 'void read()':
sure.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, 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<double, 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<double, double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         if(high >= 0 && high < bet1.size())
      |                         ~~~~~^~~~~~~~~~~~~
sure.cpp:82:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         else if(low >= 0 && low < bet1.size())
      |                             ~~~~^~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -