Submission #1164302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164302		KhoaDuy	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	67 / 100	3107 ms	5132 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
bool solve(int n,int a[],int b[],int c[],int x){
    int MaxL=0,MinR=n;
    for(int i=0;i<n;i++){
        int l,r;
        int low=i,high=n-1;
        low--,high++;
        while(high-low>1){
            int mid=((high-low)>>1)+low;
            if(a[mid]-b[i]>=-x){
                high=mid;
            }
            else{
                low=mid;
            }
        }
        l=high;
        low=i,high=n-1;
        low--,high++;
        while(high-low>1){
            int mid=((high-low)>>1)+low;
            if(a[mid]-b[i]<=x){
                low=mid;
            }
            else{
                high=mid;
            }
        }
        r=low;
        l-=i,r-=i;
        if(r==n-1-i&&abs(a[2*n-i-1]-b[i])<=x){
            r=n;
        }
        MaxL=max(MaxL,l),MinR=min(MinR,r);
    }
    for(int i=0;i<n;i++){
        int l,r;
        int low=2*n-1-i,high=2*n-1;
        low--,high++;
        while(high-low>1){
            int mid=((high-low)>>1)+low;
            if(a[mid]-c[i]<=x){
                high=mid;
            }
            else{
                low=mid;
            }
        }
        l=high;
        low=2*n-1-i,high=2*n-1;
        low--,high++;
        while(high-low>1){
            int mid=((high-low)>>1)+low;
            if(a[mid]-c[i]<-x){
                high=mid;
            }
            else{
                low=mid;
            }
        }
        r=low;
        l-=(2*n-1-i),r-=(2*n-1-i);
        if(r==2*n-1-(2*n-1-i)&&abs(c[i]-a[i])<=x){
            r=n;
        }
        MaxL=max(MaxL,l),MinR=min(MinR,r);
    }
    if(MaxL<=MinR){
        return true;
    }
    return false;
}
int calc(vector<int> a,vector<int> b){
    int curr=0;
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    for(int i=0;i<a.size();i++){
        curr=max(curr,abs(a[i]-b[i]));
    }
    return curr;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    if(n<=2000){
        vector<int> a(2*n),b(n),c(n);
        for(int i=0;i<2*n;i++){
            cin >> a[i];
        }
        for(int i=0;i<n;i++){
            cin >> b[i];
        }
        for(int i=0;i<n;i++){
            cin >> c[i];
        }
        int ans=1e9;
        for(int l=0;l<=n;l++){
            vector<int> le,ri;
            for(int i=0;i<2*n;i++){
                if(i-l>=0&&i-l<n){
                    le.push_back(a[i]);
                }
                else{
                    ri.push_back(a[i]);
                }
            }
            ans=min(ans,max(calc(le,b),calc(ri,c)));
            ans=min(ans,max(calc(le,c),calc(ri,b)));
        }
        cout << ans;
        return 0;
    }
    int a[2*n],b[n],c[n];
    for(int i=0;i<2*n;i++){
        cin >> a[i];
    }
    for(int i=0;i<n;i++){
        cin >> b[i];
    }
    for(int i=0;i<n;i++){
        cin >> c[i];
    }
    sort(b,b+n);
    sort(c,c+n);
    int low=0,high=1e9;
    low--,high++;
    while(high-low>1){
        int mid=((high-low)>>1)+low;
        if(solve(n,a,b,c,mid)||solve(n,a,c,b,mid)){
            high=mid;
        }
        else{
            low=mid;
        }
    }
    cout << high;
}

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