Submission #1154167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154167		kes0716	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	100 / 100	3090 ms	12160 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n;
pair<int, int> findrange(vector<int> &a, int crit, int cnt){
    int l = lower_bound(a.begin(), a.begin() + n, crit) - a.begin();
    int r = upper_bound(a.begin() + n, a.end(), crit, [](const int &u, const int &v){return u>v;}) - a.begin() - 1;
    //printf("l=%d r=%d crit=%d\n", l, r, crit);
    if(cnt > r-l+1) return make_pair(n+1, -1);
    int lo = (l + cnt - 1) - n + 1;
    int hi = r - cnt + 1;
    return make_pair(max(lo, 0), min(hi, n));
}
bool possible(vector<int> &b, vector<int> &ab, vector<int> &c, vector<int> &ac, int err){
    int lb = n, rb = 0;
    pair<int, int> val = make_pair(0, n);
    int i;
    for(i=0; i<n; i++){
        auto tmp = findrange(ab, b[i] - err, i+1);
        val.first = max(val.first, tmp.first);
        val.second = min(val.second, tmp.second);
        tmp = findrange(ab, b[i] + err + 1, i+1);
        lb = min(tmp.first - 1, lb);
        rb = max(tmp.second + 1, rb);
        tmp = findrange(ac, c[i] - err, i+1);
        val.first = max(val.first, tmp.first);
        val.second = min(val.second, tmp.second);
        tmp = findrange(ac, c[i] + err + 1, i+1);
        lb = min(tmp.first - 1, lb);
        rb = max(tmp.second + 1, rb);
        if(val.first > val.second) return false;
        if(val.first > lb && val.second < rb) return false;
    }
    //printf("err=%d val.first=%d val.second=%d lb=%d rb=%d\n", err,val.first,val.second,lb,rb);
    return val.first <= lb || val.second >= rb;
}
int main(){
    int i, v;
    vector<int> a, as, ar, b, c, negb, negc;
    scanf("%d", &n);
    a.resize(2*n);
    as.resize(2*n);
    ar.resize(2*n);
    b.resize(n);
    c.resize(n);
    negb.resize(n);
    negc.resize(n);
    for(i=0; i<2*n; i++){
        scanf("%d", &a[i]);
        as[i] = a[i];
        ar[(i+n)%(2*n)] = -a[i];
    }
    for(i=0; i<n; i++){
        scanf("%d", &b[i]);
        negb[i] = -b[i];
    }
    for(i=0; i<n; i++){
        scanf("%d", &c[i]);
        negc[i] = -c[i];
    }
    sort(b.begin(), b.end(), [](int &u, int &v){return u>v;});
    sort(negb.begin(), negb.end(), [](int &u, int &v){return u>v;});
    sort(c.begin(), c.end(), [](int &u, int &v){return u>v;});
    sort(negc.begin(), negc.end(), [](int &u, int &v){return u>v;});
    int lo = 0, hi = 1'000'000'009, mid;
    while(lo < hi){
        mid = (lo+hi)/2;
        if(possible(b, as, negc, ar, mid) || possible(negb, ar, c, as, mid))
            hi = mid;
        else lo = mid+1;
    }
    printf("%d\n", lo);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d", &b[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d", &c[i]);
      |         ~~~~~^~~~~~~~~~~~~

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