VOI 08 nksgame

Code

#include             <bits/stdc++.h>
#define pb           push_back
#define fi           first
#define se           second
#define int          long long 
#define pii          pair<long long, long long>
#define endl         "\n"
#define TIME         (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i)      (1ll<<(i))
#define FILE(A)      freopen(A".INP", "r", stdin); freopen(A".OUT", "w", stdout)
#define BIT(Mask, i) (((Mask)>>(i))&1)

using namespace std;

const int N    = 1e5+5;
const int MOD  = 1e9+7;
const int INF  = 1e16 ;
const int Lim  = 1e9  ;
const int BASE = 31   ;

int n, a[N], b[N];

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    cin >> n;
    for (int i=1;i <= n;i++)
        cin >> a[i];
    for (int i=1;i <= n;i++)
        cin >> b[i];    
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    int ans = INF;
    b[n+1] = b[0] = INF;
    for (int i=1,j=1;i <= n;i++) {
        int l=1,r = n;
        while(l <= r) {
            int mid = l + (r-l)/2;
            if (b[mid] >= -a[i]) {
                l = mid+1;
            }
            else r = mid-1;
            ans = min(ans, abs(a[i] + b[mid]));
        }
        l=1,r = n;
        while(l <= r) {
            int mid = l + (r-l)/2;
            if (b[mid] >= -a[i]) {
                r = mid-1;
            }
            else l = mid+1;
            ans = min(ans, abs(a[i] + b[mid]));
        }
    }
    cout << ans;

    cerr << "Time elapsed: " << TIME << "s.\n";
    return 0;
}

// Nguyen Minh Hieu - 2008 - Gia Lai.
// https://hieuhfgr.pythonanywhere.com/
// .-.. --- ...- . .-.. -.--