oj.uz

Submission #92656

# Submission time Handle Problem Language Result Execution time Memory
92656 2019-01-04T09:35:45 Z LittleFlowers__ Watching (JOI13_watching) C++14
0 / 100
 3 ms 376 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=500010;
int n,p,q;
int a[N];
int b[N];
bool C(int x)
{
    int P=p,Q=q,i=1;
    while(i<=n)
    {
        if(!P && !Q) return 0;
        if(a[i]+x*2-1<a[i+1]) (P>0 ? P : Q)--,i++;
        else
        {
            int u=-1,v=-1;
            if(Q) u=upper_bound(a+1,a+n+1,a[i]+x*2-1)-a;
            if(P) v=upper_bound(a+1,a+n+1,a[i]+x-1)-a;
            if(u>v) Q--,i=u;
            else    P--,i=v;
        }
    }
    return 1;
}
bool D(int x)
{
    int P=p,Q=q,i=1;
    while(i<=n)
    {
        if(!P && !Q) return 0;
        if(b[i]+x*2-1<b[i+1]) (P>0 ? P : Q)--,i++;
        else
        {
            int u=-1,v=-1;
            if(Q) u=upper_bound(b+1,b+n+1,b[i]+x*2-1)-b;
            if(P) v=upper_bound(b+1,b+n+1,b[i]+x-1)-b;
            if(u>v) Q--,i=u;
            else    P--,i=v;
        }
    }
    return 1;
}
main()
{
    //freopen("WATCHING.inp","r",stdin);
    cin>>n>>p>>q;
    for(int i=1; i<=n; ++i) cin>>a[i];
    sort(a+1,a+n+1);
    int cur=a[n];
    for(int i=1; i<=n; ++i) b[i]=cur-a[n-i+1];
    a[n+1]=b[n+1]=1e18;
    int l=1,m,r=1e9,ans;
    while(l<=r)
    {
        m=l+(r-l)/2;
        if(C(m) || D(m)) ans=m,r=m-1;
        else l=m+1;
    }
    cout<<ans;
}

Compilation message

watching.cpp:44:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
0 / 50.0

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

Subtask #2
0 / 50.0

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