Submission #1229072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229072		unnick	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	147 ms	2372 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

typedef long long int ll;

using namespace std;

int mod(int x, int y) {
    return ((x%y)+y)%y;
}
int dist(int n, int x, int y) {
    return min(mod(x-y,n*2),mod(y-x,n*2));
}
// int dist2(int n, int x, int y) {
//     return min(mod(x-y,n),mod(y-x,n));
// }

int dkl(vector<int> &k, int n, int i) {
    int a = i >= n ? n : 0;
    i -= a;
    int j = distance(k.begin(), upper_bound(k.begin(), k.end(), i));
    if (j == 0) return k.back() - n + a;
    return k[j-1] + a;
}
int dkr(vector<int> &k, int n, int i) {
    int a = i >= n ? n : 0;
    i -= a;
    int j = distance(k.begin(), lower_bound(k.begin(), k.end(), i));
    if (j == k.size()) return k.front() + n + a;
    return k[j] + a;
}

// #define dbg(v) cout << #v << " = " << v << "\n"

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> k(m);
    for (int i = 0; i < m; i++) {
        cin >> k[i];
    }
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        int r = dist(n, x, y);
        // dbg(dkl(k,n,x));
        { int tmp = dkl(k, n, x); r = min(r, dist(n, x, tmp) + dist(n, tmp+n, y) + 1); }
        { int tmp = dkr(k, n, x); r = min(r, dist(n, x, tmp) + dist(n, tmp+n, y) + 1); }
        { int tmp = dkl(k, n, y); r = min(r, dist(n, x, tmp+n) + dist(n, tmp, y) + 1); }
        { int tmp = dkr(k, n, y); r = min(r, dist(n, x, tmp+n) + dist(n, tmp, y) + 1); }
        cout << r << "\n";
    }

    // vector<int> dfl;
    // vector<int> dfr;
    // for (int j = 0; j < 2; j++) {
    //     int dl = 20000;
    //     int dr = 0;
    // }
    return 0;
}

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