Searching for Soulmates (C++11)

Falin Yu (lisayu999)
Submitted: Sun, Jan 30, 2022 23:41:52 EST
Contest: USACO 2022 January Contest, Silver

/*
Jan. 2022, silver, problem 1
*/
#include <bits/stdc++.h>
using namespace std;
// to be strict, to hold 10^18
#define LL long long
pair<LL,int> next(LL l, int move) {
    if(l%2==0) {
        return {l/2,1};
    } else {
        return {(l+move)/2,2};
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;

    for(int i=0; i<N; i++) {
        LL p1, p2;
        int changes = 0;
        cin >> p1 >> p2;
        // move p1 forward to be less than p2
        while(p1>p2) {
            pair<LL,int> n = next(p1, 1);
            p1 = n.first;
            changes += n.second;
        }
        if(p1==p2) {
            cout << 0 << endl;
            continue;
        }
        // move p2 backward to larger than p1
        
        for(;;){
            pair<LL,int> n = next(p2, -1);
            if(n.first > p1) {
                p2 = n.first;
                changes += n.second;
            } else break;
        }
        
        // find the closest distance of numbers in p1,p2 possible change series
        for(;;) {
            pair<LL,int> n1 = next(p1, 1);
            pair<LL,int> n2 = next(p2, -1);
            int delta = n2.second+n1.second;
            // keep moving two pointers when changes could be less
            if ( n2.first-n1.first + delta < p2-p1 ) {
                p1 = n1.first;
                p2 = n2.first;
                changes += delta;
            } else {
                // no better movement of backward/forward
                changes += (p2-p1);
                break;
            }
        }
        cout << changes << endl;
    }
}