[Hackerearth] Farthest Coprime

Problem Link    : Farthest Coprime
Category        : Add Hoc
Contest         : January Easy '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int maxn = 1e3 + 5;
 
using pii = pair<int, int>;
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("c2.txt", "r", stdin);
        freopen("c2-out.txt", "w", stdout);
    }
 
    int n, q;
    cin >> n >> q;
    vector<int> arr(n + 1);
    map<int, vector<int>> cache;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        cache[ arr[i] ].push_back(i);
    }
    vector<vector<pii>> queries(maxn);
    vector<int> ans(q, -1);
    for (int i = 0; i < q; i++) {
        int pos;
        cin >> pos;
        queries[ arr[pos] ].push_back({pos, i});
    }
    for (int i = 1; i < maxn; i++) {
        if (queries[i].size() == 0) {
            continue;
        }
        int minPos = n + 1;
        int maxPos = -1;
        for (auto it : cache) {
            if (__gcd(i, it.first) > 1) {
                continue;
            }
            minPos = min(minPos, it.second[0]);
            maxPos = max(maxPos, it.second.back());
        }
        if (maxPos != -1) {
            for (pii p : queries[i]) {
                int diff = max(abs(p.first - minPos), abs(p.first - maxPos));
                if (abs(p.first - minPos) > abs(p.first - maxPos)) {
                    ans[p.second] = minPos;
                } else if (abs(p.first - maxPos) > abs(p.first - minPos)) {
                    ans[p.second] = maxPos;
                } else {
                    ans[p.second] = min(minPos, maxPos);
                }
            }
        }
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << " ";
    }
}