Submission #1229054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229054		gry3125	Circle Passing (EGOI24_circlepassing)	C++20	31 / 100	217 ms	16920 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 < 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); 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 = 2*m-1;
	        while (L < R) {
	        	ll m = (L + R + 1) / 2;
	        	if (e[m] > x) R = m-1;
	        	else L = m;
	        }
	        ll d1, d2;
	        if (e[L] >= 2*n) {
	        	d1 = e[L] - 2*n;
	        	d2 = e[L] - n;
	        } else if (e[L] < n) {
	        	d1 = e[L]; 
	        	d2 = e[L] + n;
	        } else {
	        	d1 = e[L];
	        	d2 = e[L] - n;
	        }
	        ans = min(ans, d(x, d1)+d(y, d2)+1);
        }
        
        if (1) {
	        ll L = 0, R = 2*m-1;
	        while (L < R) {
	        	ll m = (L + R) / 2;
	        	if (e[m] < x) L = m+1;
	        	else R = m;
	        }
	        ll d1, d2;
	        if (e[L] >= 2*n) {
	        	d1 = e[L] - 2*n;
	        	d2 = e[L] - n;
	        } else if (e[L] < n) {
	        	d1 = e[L]; 
	        	d2 = e[L] + n;
	        } else {
	        	d1 = e[L];
	        	d2 = e[L] - n;
	        }
	        ans = min(ans, d(x, d1)+d(y, d2)+1);
        }
        
        cout << ans << "\n";
    }
    return 0;
}

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