Submission #1248065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248065		mosesmayer	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	19 ms	4512 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef vector<int> vi;

template<class T> inline T re(){
    T N = 0; char c = getchar(); bool neg = 0;
    for (; c < '0' || c > '9'; c = getchar()) neg |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        N = (N<<3)+(N<<1) + c - '0';
    return neg ? -N : N;
}

const int MX = 5e5;
int n, m, q, ks[2 * MX + 5];

int main() {
    n = re<int>(); m = re<int>(); q = re<int>();
    for (int i = 1; i <= m; i++) {
        ks[i] = re<int>();
        ks[i + m] = ks[i] + n;
    }
    function<LL(LL, LL)> get_direct = [&](LL x, LL y) {
        LL cw = (-x + n + n + y) % (2LL * n);
        LL ccw = (x + n + n - y) % (2LL * n);
        return min(cw, ccw);
    };
    for (int qq = 1, x, y; qq <= q; qq++) {
        x = re<LL>(); y = re<LL>();
        // find closest
        LL cw, ccw;
        if (x <= ks[1] || x >= ks[m * 2]) {
            cw = ks[1], ccw = ks[m * 2];
        } else {
            cw = *(lower_bound(ks + 1, ks + m + m + 1, x));
            ccw = lower_bound(ks + 1, ks + m + m + 1, x) - ks;
            if (ccw == 1) ccw = ks[m * 2];
            else ccw = ks[ccw - 1];
        }
        // cerr << cw << ' ' << ccw << '\n';
        printf("%lld\n", min({get_direct(x, y), get_direct(x, cw) + 1 + get_direct((cw + n) % (2LL * n), y),
                                                get_direct(x, ccw) + 1 + get_direct((ccw + n) % (2LL * n), y)}));
    }
    return 0;
}

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