Submission #92656

#	Time	Username	Problem	Language	Result	Execution time	Memory
92656		LittleFlowers__	Watching (JOI13_watching)	C++14	0 / 100	3 ms	376 KiB

watching

#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 (stderr)

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

• Subtask 1: 0 / 50
• Subtask 2: 0 / 50