Submission #1011310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011310		Pacybwoah	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	0 / 100	683 ms	19232 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cmath>
typedef long long ll;
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> vec(2 * n + 1);
    for(int i = 1; i <= 2 * n; i++) cin >> vec[i];
    vector<int> b(n + 1), c(n + 1);
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) cin >> c[i];
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    int l = 0, r = 1e9;
    while(l < r){
        int mid = (l + r) >> 1;
        bool flag = 0;
        for(int t = 0; t < 2; t++){
            vector<bool> pre_good(2 * n + 1), post_good(2 * n + 1);
            for(int i = 1; i <= n; i++){
                if(abs(b[i] - vec[i]) <= mid) pre_good[i] = 1;
                if(i > 1) pre_good[i] = (pre_good[i] && pre_good[i - 1]);
            }
            for(int i = n + 1; i <= 2 * n; i++){
                if(abs(c[2 * n + 1 - i] - vec[i]) <= mid) pre_good[i] = 1;
                if(i > n + 1) pre_good[i] = (pre_good[i] && pre_good[i - 1]);
            }
            int lptr = 1, rptr = 0, al, ar;
            vector<int> d(2 * n + 1);
            for(int i = 1; i <= n; i++){
                while(lptr <= n && abs(c[lptr] - vec[i]) > mid) lptr++;
                if(lptr > rptr) rptr = lptr;
                while(rptr < n && abs(c[rptr + 1] - vec[i]) <= mid) rptr++;
                al = i - rptr + 1, ar = i - lptr + 1;
                if(lptr > n) continue;
                al = max(1, al);
                ar = min(n, ar);
                if(al > ar) continue;
                d[al]++;
                if(ar < n) d[ar + 1]--;
            }
            for(int i = 1; i <= n; i++) d[i] += d[i - 1];
            for(int i = 1; i <= n; i++) if(d[i] == n - i + 1) post_good[i] = 1;
            lptr = 1, rptr = 0;
            for(int i = 2 * n; i > n; i--){
                while(lptr <= n && abs(b[lptr] - vec[i]) > mid) lptr++;
                if(lptr > rptr) rptr = lptr;
                while(rptr < n && abs(b[rptr + 1] - vec[i]) <= mid) rptr++;
                if(lptr == n + 1) continue;

                al = i + lptr - n, ar = i + rptr - n;
                //cout << i << " " << vec[i] << " " << lptr << " " << rptr << " " << al << " " << ar << "\n";
                al = max(n + 1, al);
                ar = min(2 * n, ar);
                if(al > ar) continue;
                d[al]++;
                if(ar < 2 * n) d[ar + 1]--;
            }
            for(int i = n + 2; i <= 2 * n; i++) d[i] += d[i - 1];
            for(int i = n + 1; i <= 2 * n; i++) if(d[i] == 2 * n - i + 1) post_good[i] = 1;
            for(int i = 1; i < n; i++){
                if(pre_good[i] && pre_good[n + i] && post_good[i + 1] && post_good[n + i + 1]) flag = 1;
            }
            if(pre_good[n] && pre_good[2 * n]) flag = 1;
            swap(b, c);
            //cout << pre_good[1] << " " << pre_good[10] << " " << post_good[2] << " " << post_good[11] << "\n";
        }
        if(flag){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    cout << l << "\n";
}
// g++ pC.cpp -std=c++17 -Wshadow -Wall -fsanitize=undefined -fsanitize=address -o run 

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