558C - Amr and Chemistry - CodeForces Solution

#include <bits/stdc++.h>
#include <cmath>
#include <iostream>
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vd vector<double>
#define vii vector<pii>
#define vll vector<pll>
#define vvi vector<vi>
#define x first
#define y second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define fore(i, l, r) for (int i = int(l); i < int(r); i++)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
// #define forn(i, a, b) for (int i = int(a); i < int(b); i++)
#define sz(a) int(a.size())
#define max(a, b) ((a) > (b) ? (a) : (b))
#define M_PI 3.14159265358979323846
template <typename X>
inline X abs(const X& a) { return a < 0 ? -a : a; }
#define MIN(a, b) (a) < (b) ? (a) : (b)
#define MAX(a, b) (a) > (b) ? (a) : (b)
#define ABS(a) (a) > 0 ? (a) : -(a)

using namespace std;
// ============================================================
template <typename DataType>
void show_(const vector<DataType>& arr, string s = "")
{
    cout << s << " ";
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << ", ";
    }
    cout << endl;
}
// cout << fixed << setprecision(10);

typedef long long ll;
const int INF = ll(2e9 + 5);
const ll INF64 = ll(1e18);

const int MAX_N = 2005;
const int MOD = 1e9 + 7;
const int LOG = 18;
const int inf = 2e9 + 4;
// const ll mx = 100000000000LL;

const int N = 2e5 + 5;

ll cnt[N]; // стоимость финального исхода 
ll all[N]; // число попаданий из разных чисел
ll vis[N]; // уже помеченные числа (которые мы уже получили)

// i -- номер числа, из которого стартуем
// x -- текущее число
// с -- стоимость проделанного пути до c
void dfs(ll i, ll x, ll c = 0) {
    if(x >= 2e5 + 5 || vis[x] == i) {
        // vis[x] == i значит, что мы уже попадали в x из числа номер a[i]
        // x > 2e5 + 5 -- начинаем обрабатывать числа, которые точно не нужны
        return;
    }
    all[x]++;
    cnt[x] += c; // добавляем стоимость попадания в x из a[i]
    vis[x] = i;  // помечаем, что мы попали в x из a[i]
    // if (x == 0) return; // избавляемся от потенциально бесконечного bfs цикла

    dfs(i, 2 * x, c + 1);
    dfs(i, x / 2, c + 1);
}

int main()
{
    ios::sync_with_stdio(false);

    int n; cin >> n;
    ll x;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        dfs(i + 1, x);
    }

    ll ans = INF64;

    for (int i = 0; i <= 2e5; ++i) {
        if (all[i] == n) {
            ans = min(ans, cnt[i]);
        }
    }
    cout << ans << endl;

    return 0;
}