Submission #1151462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151462		Ghulam_Junaid	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	312 ms	47596 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int n, m, q;
set<int> st;
int get(int x, int y){
    if (x >= y) swap(x, y);
    return min(y - x, 2 * n - (y - x));
}

int real_get(int x, int y){
    int res = get(x, y);
    if (st.find(x) != st.end())
        x += ((x >= n) ? -n : n);
    res = min(res, 1 + get(x, y));
    return res;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 0; i < m; i ++){
        int x;
        cin >> x;
        st.insert(x);
        st.insert(x + ((x >= n) ? -n : n));
    }

    for (int i = 0; i < q; i ++){
        int x, y;
        cin >> x >> y;

        int ans = real_get(x, y);
        
        auto it = st.lower_bound(x);
        if (it != st.end())
            ans = min(ans, real_get(x, *it) + real_get(*it, y));

        if (it != st.begin()){
            it--;
            ans = min(ans, real_get(x, *it) + real_get(*it, y));
        }

        ans = min(ans, real_get(x, *st.begin()) + real_get(*st.begin(), y));
        ans = min(ans, real_get(x, *st.rbegin()) + real_get(*st.rbegin(), y));

        cout << ans << '\n';
    }
}

• Subtask 1: 14 / 14
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 17 / 17
• Subtask 5: 27 / 27