Submission #879368

#	Time	Username	Problem	Language	Result	Execution time	Memory
879368		vjudge1	Sure Bet (CEOI17_sure)	C++17	20 / 100	1 ms	348 KiB

sure

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define lld long long double
#define pb push_back
#define pf push_front
#define all(a) a.begin(),a.end()
#define IShowSpeed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int N=5e5+10;
const int mod=1e9+7;
vector<double>v1,v2;

int main()
{
    IShowSpeed
    int n,x1,y1;
    cin>>n;
    while(n--)
    {
        double x,y;
        cin>>x>>y;
        v1.pb(x);
        v2.pb(y);
    }
    sort(all(v1));
    sort(all(v2));
    reverse(all(v1));
    reverse(all(v2));
    for(int i=1;i<v1.size();i++) v1[i]+=v1[i-1];
    for(int i=1;i<v2.size();i++) v2[i]+=v2[i-1];
    double ans=0;
    for(int i=0;i<v1.size();i++)
    {
        int l=0,r=v1.size()-1,pos=-1;
        while(l<=r)
        {
            int m=(l+r) >> 1;
            double lol=i+m+2;
            if(v1[i]>=lol) l=m+1,pos=m,ans=max(ans,min(v1[i]-lol,v2[m]-lol));
            else r=m-1;
        }
        l=0,r=pos;
        while(l<=r)
        {
            int m=(l+r) >> 1;
            double lol=i+m+2;
            if(v2[m]<lol || v2[m]>=v1[i]) r=m-1;
            else l=m+1,ans=max(ans,min(v1[i]-lol,v2[m]-lol));
        }
    }
    cout<<fixed<<setprecision(4)<<ans;
}
/*
100
12.0 16.8
6.0 16.4
19.6 10.0
3.1 10.8
5.9 18.7
4.8 19.4
7.1 15.5
18.9 11.9
14.0 10.2
4.7 11.1
8.6 12.0
8.9 6.8
14.3 10.3
5.8 1.5
4.0 4.1
12.6 3.3
17.5 0.2
6.3 10.0
12.4 6.7
0.6 4.6
8.5 15.1
12.2 7.5
13.1 11.8
5.4 10.0
16.6 8.6
19.3 1.7
15.4 18.4
17.5 5.0
3.5 6.5
5.3 10.0
12.7 2.4
19.9 19.4
13.8 1.4
18.8 9.8
13.3 4.2
9.9 16.8
7.2 17.9
3.4 4.6
7.3 11.4
4.2 10.9
6.9 4.2
18.1 1.1
6.1 2.3
9.3 13.3
7.9 15.1
7.6 11.1
16.0 5.2
9.8 3.5
4.4 3.4
12.4 5.3
1.0 2.8
1.8 1.4
9.5 17.7
17.8 19.4
12.5 5.4
1.4 3.0
7.6 5.8
0.4 6.3
11.3 3.1
12.6 11.9
19.5 9.0
5.3 11.5
6.4 6.4
18.5 1.0
14.9 2.9
18.1 19.3
17.3 6.0
12.4 15.1
18.1 5.8
3.6 7.7
16.0 0.8
6.8 2.0
19.3 11.9
17.7 8.8
8.8 17.1
15.4 10.0
14.8 13.2
2.7 15.3
0.5 11.0
7.4 12.4
12.5 15.7
11.3 1.2
3.8 15.4
2.4 18.2
10.6 15.3
12.1 16.9
15.3 16.8
15.8 9.4
10.0 7.8
2.2 15.1
17.6 17.8
1.9 18.9
4.9 6.1
7.4 17.3
1.2 14.0
18.0 17.4
9.2 17.4
19.2 1.1
9.6 1.7
8.0 15.3
801.2000
*/

Compilation message (stderr)

sure.cpp: In function 'int main()':
sure.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=1;i<v1.size();i++) v1[i]+=v1[i-1];
      |                 ~^~~~~~~~~~
sure.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=1;i<v2.size();i++) v2[i]+=v2[i-1];
      |                 ~^~~~~~~~~~
sure.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<v1.size();i++)
      |                 ~^~~~~~~~~~
sure.cpp:16:11: warning: unused variable 'x1' [-Wunused-variable]
   16 |     int n,x1,y1;
      |           ^~
sure.cpp:16:14: warning: unused variable 'y1' [-Wunused-variable]
   16 |     int n,x1,y1;
      |              ^~

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