CFR Educational 6 D. Professor GukiZ and Two Arrays ( lower_bound )

Problem - D - Codeforces
We can simply brute force for 0 and 1 swap, so let's think about 2 swaps. When 2 swaps are committed, and given that asum is the sum for all elements in a, same for bsum, swapping ( i, j ) in A with ( x, y ) in B, and without losing generality let asum ≥ bsum, we will have the new final cost as
new_cost = [ asum - bsum + 2*( b[x] + b[y] ) ] - 2*( a[i] + a[j] )
If ( x, y ) is fixed, we will simply have to find ( i, j ) that produces 2*( a[i] + a[j] ) nearest to the value in the angled bracket. This can be achieved easily with preprocessing and set::lower_bound.

typedef ll T_triplet;
struct triplet{
    T_triplet first, second, third;
    triplet(){}
    triplet( T_triplet _f, T_triplet _s, T_triplet _t ){
        first = _f, second = _s, third = _t;
    }
    bool operator < ( const triplet &oth ) const{
        if( first != oth.first ) return first < oth.first;
        if( second != oth.second ) return second < oth.second;
        return third < oth.third;
    }
};

const ll LINF = 1LL << 60;

void solve(){
    int N; cin >> N;
    vi A( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];

    int M; cin >> M;
    vi B( M );
    for( int i = 0; i < M; ++i )
        cin >> B[ i ];

    ll asum = 0, bsum = 0;
    for( int i = 0; i < N; ++i ) asum += A[ i ];
    for( int i = 0; i < M; ++i ) bsum += B[ i ];
    ll min_cost = abs( asum - bsum );

    bool is_swapped = false;
    if( not ( asum >= bsum ) ) // to make things a little easier( ? )
        is_swapped = true,
        swap( N, M ),
        swap( asum, bsum ),
        swap( A, B );

    vp pair2swap;

    for( int i = 0; i < N; ++i )
        for( int j = 0; j < M; ++j ){
            ll nasum = asum - A[ i ] + B[ j ];
            ll nbsum = bsum - B[ j ] + A[ i ];
            if( abs( nasum - nbsum ) < min_cost )
                min_cost = abs( nasum - nbsum ),
                pair2swap = { pii( i, j ) };
        }

    set< triplet > ast;
    for( int i = 0; i < N; ++i )
        for( int j = i + 1; j < N; ++j )
            ast.insert( triplet( 2LL * ( A[ i ] + A[ j ] ), i, j ) );
    for( int i = 0; i < M; ++i )
        for( int j = i + 1; j < M; ++j ){
            if( ast.empty() ) break;
            ll z = asum - bsum + 2LL * ( B[ i ] + B[ j ] );
            auto it = ast.lower_bound( triplet( z, -1, -1 ) );
            if( it == ast.end() ){
                --it;
                ll score = abs( z - it->first );
                if( score < min_cost )
                    min_cost = score,
                    pair2swap = { pii( it->second, i ), pii( it->third, j ) };
            } else{
                ll score = abs( z - it->first );
                if( score < min_cost )
                    min_cost = score,
                    pair2swap = { pii( it->second, i ), pii( it->third, j ) };
                if( it != ast.begin() ){
                    --it;
                    score = abs( z - it->first );
                    if( score < min_cost )
                        min_cost = score,
                        pair2swap = { pii( it->second, i ), pii( it->third, j ) };
                }
            }
        }

    cout << min_cost << "\n";
    cout << pair2swap.size() << "\n";
    for( int i = 0; i < pair2swap.size(); ++i ){
        if( is_swapped )
            cout << pair2swap[ i ].second + 1 << " " << pair2swap[ i ].first + 1 << "\n";
        else
            cout << pair2swap[ i ].first + 1 << " " << pair2swap[ i ].second + 1 << "\n";
    }
}