oj.uz

Submission #879369

# Submission time Handle Problem Language Result Execution time Memory
879369 2023-11-27T08:32:31 Z strelok1337 Sure Bet (CEOI17_sure) C++17
20 / 100
 0 ms 348 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -