제출 #1229096

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229096		gry3125	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	246 ms	16796 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define ll long long int
using namespace std;

ll n, m, q;

ll d(ll x, ll y) {
	if (x >= 2*n) x -= 2*n;
	if (y >= 2*n) y -= 2*n;
	if (x < 0) x += 2*n;
	if (y < 0) y += 2*n;
	if (x < y) swap(x, y); // x > y
	return min(x-y, 2*n-(x-y));
}

int main() {
    cin >> n >> m >> q;
    vector<ll> e;
    for (ll i = 0; i < m; i++) {
        ll x; cin >> x;
        e.pb(x-n); e.pb(x); e.pb(x+n); e.pb(x+2*n);
    }
    sort(all(e));
    
    while (q--) {
        ll x, y; cin >> x >> y; 
        if (x < y) swap(x, y); // x > y
        ll ans = d(x, y); // no jump
        
        if (1) {
	        ll L = 0, R = e.size()-1;
	        while (L < R) {
	        	ll m = (L + R + 1) / 2;
	        	if (e[m] > x) R = m-1;
	        	else L = m;
	        }
	        ans = min(ans, d(x, e[L])+d(y, e[L]-n)+1);
        }
        
        if (1) {
	        ll L = 0, R = e.size()-1;
	        while (L < R) {
	        	ll m = (L + R) / 2;
	        	if (e[m] < x) L = m+1;
	        	else R = m;
	        }
	        ans = min(ans, d(x, e[L])+d(y, e[L]-n)+1);
        }
        
        cout << ans << "\n";
    }
    return 0;
}

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