Submission #1165513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165513		Tony1234	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	87 ms	16228 KiB

Main

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#ifdef _debug 
#include </home/tony/templates/debug.cpp>
#else
#define debug(...) 42
#endif

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define vi vector<int>
#define vt vector
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7, inf = (int)2e9;
const ll infll = (ll)1e18;
#define int ll
void solve(){
    int N, M, Q; cin >> N >> M >> Q;
    vector<int> K(M);
    for(auto &u : K)cin >> u;
    for(int i = 0; i < M; i++){
        K.push_back(K[i]+N);
    }
    //theres 2N people btw
    for(int i = 0; i < 2 * M; i++){
        K.push_back(K[i] + N * 2);
    }
    auto find_next = [&](int s) -> int{
        int ind = lower_bound(all(K), s) - K.begin();
        int ans = K[ind]; 
        if(ans >= 2 * N)ans -= 2*N; 
        return ans; 
    };
    auto find_prev = [&](int s) -> int{
        s += 2*N; 
        int ind = upper_bound(all(K), s) - K.begin() - 1;
        int ans = K[ind];
        if(ans >= 2 * N)ans -= 2*N;
        return ans; 
    };
    auto get_dist = [&](int s, int s2) -> int{
        return min(abs(s-s2), 2*N-abs(s-s2));
    };
    while(Q--){
        int x, y; cin >> x >> y;
        vi L, R;
        L.pb(find_next(x)); L.pb(find_prev(x));
        L.pb(find_next(x+1)); L.pb(find_prev(x-1));
        R.pb(find_next(y)); R.pb(find_next(y));
        R.pb(find_next(y+1)); R.pb(find_prev(y-1));
        int ans = get_dist(x,y);
        auto mv = [&](int r) -> int{
            vi mo; mo.pb(r); 
            if(r > N - 1)mo.pb(r - N);
            else mo.pb(r + N);
            if(mo[0] > mo[1])swap(mo[0], mo[1]);
            int me = infll;
            me = min(me, get_dist(x, mo[0]) + get_dist(y, mo[1]) + 1);
            swap(mo[0], mo[1]);
            me = min(me, get_dist(x, mo[0]) + get_dist(y, mo[1]) + 1);
            return me; 
        };
        for(auto u : L)ans = min(ans, mv(u));
        for(auto u : R)ans = min(ans, mv(u));
        cout << ans << '\n';
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    solve();
}

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