oj.uz

Submission #1066071

# Submission time Handle Problem Language Result Execution time Memory
1066071 2024-08-19T14:43:39 Z NemanjaSo2005 Growing Vegetables is Fun 5 (JOI24_vegetables5) C++17
37 / 100
 2519 ms 19744 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4696 KB Output is correct
2 Correct 4 ms 2652 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 4 ms 2652 KB Output is correct
7 Correct 4 ms 2832 KB Output is correct
8 Correct 4 ms 2648 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 4 ms 2768 KB Output is correct
11 Correct 4 ms 2652 KB Output is correct
12 Incorrect 4 ms 2648 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4696 KB Output is correct
2 Correct 4 ms 2652 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 4 ms 2652 KB Output is correct
7 Correct 4 ms 2832 KB Output is correct
8 Correct 4 ms 2648 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 4 ms 2768 KB Output is correct
11 Correct 4 ms 2652 KB Output is correct
12 Incorrect 4 ms 2648 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4696 KB Output is correct
2 Correct 4 ms 2652 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 4 ms 2652 KB Output is correct
7 Correct 4 ms 2832 KB Output is correct
8 Correct 4 ms 2648 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 4 ms 2768 KB Output is correct
11 Correct 4 ms 2652 KB Output is correct
12 Incorrect 4 ms 2648 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2519 ms 18984 KB Output is correct
2 Correct 2291 ms 15572 KB Output is correct
3 Correct 1836 ms 13488 KB Output is correct
4 Correct 2395 ms 19064 KB Output is correct
5 Correct 2185 ms 15576 KB Output is correct
6 Correct 59 ms 5160 KB Output is correct
7 Correct 1870 ms 19744 KB Output is correct
8 Correct 1789 ms 14424 KB Output is correct
9 Correct 2382 ms 19028 KB Output is correct
10 Correct 2456 ms 19100 KB Output is correct
11 Correct 2388 ms 18916 KB Output is correct
12 Correct 2279 ms 16724 KB Output is correct
13 Correct 2313 ms 15444 KB Output is correct
14 Correct 1730 ms 19104 KB Output is correct
15 Correct 1824 ms 15556 KB Output is correct
16 Correct 1855 ms 15596 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4696 KB Output is correct
2 Correct 4 ms 2652 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 4 ms 2652 KB Output is correct
7 Correct 4 ms 2832 KB Output is correct
8 Correct 4 ms 2648 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 4 ms 2768 KB Output is correct
11 Correct 4 ms 2652 KB Output is correct
12 Incorrect 4 ms 2648 KB Output isn't correct
13 Halted 0 ms 0 KB -