Submission #1066071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066071		NemanjaSo2005	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	37 / 100	2519 ms	19744 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=3e5+5;
int N,niz[2*maxn],R[maxn],B[maxn],pref[2*maxn];
int S;
pair<int,int> inter1(int x){
   int dg,gg,l=N+1,r=0,sred;
   dg=1;
   gg=N;
   while(dg<=gg){
      sred=(dg+gg)/2;
      if(x-S>niz[sred]){
         dg=sred+1;
      }
      else if(x+S<niz[sred]){
         gg=sred-1;
      }
      else{
         l=sred;
         gg=sred-1;
      }
   }
   dg=1;
   gg=N;
   while(dg<=gg){
      sred=(dg+gg)/2;
      if(x-S>niz[sred]){
         dg=sred+1;
      }
      else if(x+S<niz[sred]){
         gg=sred-1;
      }
      else{
         r=sred;
         dg=sred+1;
      }
   }
   return {l,r};
}
pair<int,int> inter2(int x){
   int dg,gg,l=2*N+1,r=0,sred;
   dg=N+1;
   gg=2*N;
   while(dg<=gg){
      sred=(dg+gg)/2;
      if(x+S<niz[sred]){
         dg=sred+1;
      }
      else if(x-S>niz[sred]){
         gg=sred-1;
      }
      else{
         l=sred;
         gg=sred-1;
      }
   }
   dg=N+1;
   gg=2*N;
   while(dg<=gg){
      sred=(dg+gg)/2;
      if(x+S<niz[sred]){
         dg=sred+1;
      }
      else if(x-S>niz[sred]){
         gg=sred-1;
      }
      else{
         r=sred;
         dg=sred+1;
      }
   }
   return {l,r};
}
bool moze(int sred){
   memset(pref,0,sizeof(pref));
   S=sred;
   /// R, koji ce biti u onih N
   for(int i=1;i<=N;i++){
      auto a = inter1(R[i]);
      if(a.f<=a.s){
         pref[max(1,a.f-i+1)]++;
         pref[max(1,a.s-i+1+1)]--;
      }
      int poz=2*N-i+1;
      if(R[i]-S<=niz[poz] and R[i]+S>=niz[poz]){
         pref[poz-N+1]++;
      }
   }
   /// B, ostali
   for(int i=1;i<=N;i++){
      if(B[i]-S<=niz[i] and B[i]+S>=niz[i])
         pref[i+1]++;
      auto b=inter2(B[i]);
      if(b.f<=b.s){
         pref[max(1,i-(2*N-b.f+1)+1)]++;
         pref[max(1,i-(2*N-b.s+1)+1+1)]--;
      }
   }
   int v=0;
   for(int i=1;i<=N;i++){
      v+=pref[i];
      if(v==2*N)
         return true;
   }
   return false;
}
int resi(){
   int dg=0,gg=1e9,sred,ret;
   while(dg<=gg){
      sred=(dg+gg)/2;
      if(moze(sred)){
         ret=sred;
         gg=sred-1;
      }
      else
         dg=sred+1;
   }
   return ret;
}
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cin>>N;
   for(int i=1;i<=2*N;i++)
      cin>>niz[i];
   for(int i=1;i<=N;i++)
      cin>>R[i];
   for(int i=1;i<=N;i++)
      cin>>B[i];
   sort(R+1,R+1+N);
   sort(B+1,B+1+N);
   int res=resi();
   for(int i=1;i<=N;i++)
      swap(R[i],B[i]);
   res=min(res,resi());
   cout<<res<<"\n";
}

Compilation message (stderr)

Main.cpp: In function 'int resi()':
Main.cpp:121:11: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |    return ret;
      |           ^~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 21
• Subtask 4: 37 / 37
• Subtask 5: 0 / 33