oj.uz

Submission #92647

# Submission time Handle Problem Language Result Execution time Memory
92647 2019-01-04T09:21:23 Z LittleFlowers__ Watching (JOI13_watching) C++14
0 / 100
 3 ms 636 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=500010;
int n,p,q;
int a[N];
bool C(int x)
{
  ///2 ,11 ,17
  int P=p,Q=q,i=1;
  while(i<=n)
  {
    if(!P && !Q) return 0;
    //cout<<i<<" "<<P<<" "<<Q<<"\n";
    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;
         //cout<<a[i] + x*2<<" "<<a[i+1]<<"\n";
         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 l=1,m,r=1e9,ans;
  while(l<=r)
  {
    m=l+(r-l)/2;
    if(C(m)) ans=m,r=m-1;
    else l=m+1;
  }
  cout<<ans;
}

Compilation message

watching.cpp:36: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 636 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Incorrect 2 ms 380 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 -