Submission #1094905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094905		raphaelp	Circle Passing (EGOI24_circlepassing)	C++14	100 / 100	199 ms	13516 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int dist(int a, int b, int L)
{
    return min(max(a, b) - min(a, b), L - max(a, b) + min(a, b));
}
int main()
{
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> Tab(M);
    for (int i = 0; i < M; i++)
    {
        cin >> Tab[i];
    }
    for (int i = 0; i < M; i++)
        Tab.push_back(Tab[i] + N);
    for (int i = 0; i < 2 * M; i++)
        Tab.push_back(Tab[i] + 2 * N);
    for (int i = 0; i < Q; i++)
    {
        int x, y;
        cin >> x >> y;
        int rig = lower_bound(Tab.begin(), Tab.end(), x) - Tab.begin();
        int lef = (rig - 1 + 2 * M) % (2 * M);
        lef = Tab[lef], rig = Tab[rig] % (2 * N);
        int ans = dist(x, y, 2 * N);
        ans = min(ans, dist(x, rig, 2 * N) + 1 + dist(y, (rig + N) % (2 * N), 2 * N));
        ans = min(ans, dist(lef, x, 2 * N) + 1 + dist((lef + N) % (2 * N), y, 2 * N));
        cout << ans << '\n';
    }
}

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