Submission #1228599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228599		gry3125	Circle Passing (EGOI24_circlepassing)	C++20	14 / 100	137 ms	8616 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;

int main() {
    ll n, m, q; 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);
    }
    sort(all(e));
    while (q--) {
        ll x, y; cin >> x >> y; 
        if (x < y) swap(x, y); // x > y
        ll ox = x, oy = y;
        ll ans = min(x-y, 2*n-(x-y)); // no jump
        
        if (ans == x-y) {
            // clockwise, [x, y]
            if (y < n) y += n;
            else x -= n;
            if (x < y) swap(x, y); // x > y
            ll L = 0, R = 2*m-1;
            while (L < R) {
                ll m = (L + R) / 2;
                if (e[m] < y) L = m+1;
                else R = m;
            }
            if (e[L] <= x) ans = min(ans, x-y+1);
        } else {
            // anticlockwise [x, y]
            y += n;
            if (x < y) swap(x, y); // x > y
            ll L = 0, R = 2*m-1;
            while (L < R) {
                ll m = (L + R) / 2;
                if (e[m] < y) L = m+1;
                else R = m;
            }
            if (e[L] <= x) ans = min(ans, x-y+1);
        }
        
        x = ox; y = oy;
        if (x == y + n) {
        	if (1) {
	            ll L = 0, R = 2*m-1;
	            while (L < R) {
	                ll m = (L + R) / 2;
	                if (e[m] < y) L = m+1;
	                else R = m;
	            }
	            ll d = e[R]-y;
	            ans = min(ans, 2*d+1);
        	}
        	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 d = x-e[R];
	            ans = min(ans, 2*d+1);
        	}
        } else {
        	if (1) {
	            ll L = 0, R = 2*m-1;
	            while (L < R) {
	                ll m = (L + R) / 2;
	                if (e[m] <= y) L = m+1;
	                else R = m;
	            }
	            ans = min(ans, 2*e[L]+n-x-y+1);
        	}
        	if (1) {
        		if (x >= n) x -= n;
	            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;
	            }
	            ans = min(ans, 2*e[L]+n-ox-y+1);
        	}
        }

        cout << ans << "\n";
    }
    return 0;
}

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