Submission #1129620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129620		Hurryup_7735	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	0 / 100	183 ms	9796 KiB

Main

//What did I do to deserve it?!
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define endl '\n'
#define pb push_back
#define pf push_front
#define speedyboy ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) x.begin() , x.end()
#define allr(x) x.rbegin() , x.rend()
#define F first
#define S second
#define pll pair<ll , ll>
#define pss pair<string , string>
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;


const ll sz = 5e5 + 5 , INF = 1e18 ,  MOD = 1e9 + 7;
ll a[sz];
vector<pll> v;


ll i , j , k;
void solve() {
    ll n;
    cin >> n;
    vector<ll> a(2 * n);
    for (ll i = 0; i < 2 * n; i++) cin >> a[i];
    vector<ll> redPots(n), bluePots(n);
    for (ll i = 0; i < n; i++) cin >> redPots[i];
    for (ll i = 0; i < n; i++) cin >> bluePots[i];
    sort(all(redPots));
    sort(all(bluePots));
    sort(all(a)); // Fidanları da sıralayaq ki, performans artsın
    ll mn = INF;
    // Bütün mümkün maskaları yoxlayırıq
    for (ll mask = 0; mask < (1LL << (2 * n)); mask++) {
        // Qırmızı qabların sayı N olmalıdır
        if (__builtin_popcountll(mask) != n) continue;
        // "Gözəl düzülüş" şərtini yoxlayırıq
        bool beautiful = false;
        for (ll i = 0; i <= 2 * n - n; i++) {
            bool sameColor = true;
            ll color = (mask >> i) & 1;
            for (ll j = i; j < i + n; j++) {
                if (((mask >> j) & 1) != color) {
                    sameColor = false;
                    break;
                }
            }
            if (sameColor) {
                beautiful = true;
                break;
            }
        }
        if (!beautiful) continue;
        // Fidanları rənglərinə görə bölürük
        vector<ll> redSeeds, blueSeeds;
        for (ll i = 0; i < 2 * n; i++) {
            if ((mask >> i) & 1) {
                redSeeds.push_back(a[i]);
            } else {
                blueSeeds.push_back(a[i]);
            }
        }
        // Qrupların ölçüsünü yoxlayırıq
        if (redSeeds.size() != n || blueSeeds.size() != n) continue;
        // Fidanları sıralayırıq
        sort(all(redSeeds));
        sort(all(blueSeeds));
        // Çətinliyi hesablayırıq
        ll mx = 0;
        for (ll i = 0; i < n; i++) {
            mx = max(mx, abs(redSeeds[i] - redPots[i]));
            mx = max(mx, abs(blueSeeds[i] - bluePots[i]));
            // Əgər mx artıq mn-dən böyükdürsə, davam etməyə ehtiyac yoxdur
            if (mx >= mn) break;
        }
        mn = min(mn, mx);
    }
    cout << mn << endl;
}


signed main(){
    speedyboy;
    //open;
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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