Submission #1129637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129637		c0det1ger	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	76 ms	16228 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
 
#define int long long
#define bochi_orz cin.tie(0);cin.sync_with_stdio(0);

signed main() {
    bochi_orz
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> v(m);
    for (int i = 0; i < m; i++){
        cin >> v[i];
    }
    for (int i = 0; i < m; i++){
        v.push_back(n + v[i]);
    }
    for (int i = 0; i < 2 * m; i++){
        v.push_back(2 * n + v[i]);
    }
    while (q--){
        int x, y;
        cin >> x >> y;
        int d1 = (y + 2 * n - x) % (2 * n);
        int d2 = (x + 2 * n - y) % (2 * n);
        int k1 = *lower_bound(v.begin(), v.end(), x) % (2 * n);
        int id = lower_bound(v.begin(), v.end(), x) - v.begin();
        id %= (2 * m);
        int d3 = min((k1 + 2 * n - x) % (2 * n), (x + 2 * n - k1) % (2 * n)) + 1 + min(abs(k1 + 3 * n - y) % (2 * n), abs(y + 3 * n - k1) % (2 * n));
        id = (id + 2 * m - 1) % (2 * m);
        k1 = v[id] % (2 * n);
        //cout << k1 << "\n";
        int d4 = min((k1 + 2 * n - x) % (2 * n), (x + 2 * n - k1) % (2 * n)) + 1 + min(abs(k1 + 3 * n - y) % (2 * n), abs(y + 3 * n - k1) % (2 * n));
        cout << min({d1, d2, d3, d4}) << "\n";
    }
}
 
/*
 ____   ___    ___     ____  _____          ____    ____   ___
|      |   |  |   \   |        |     /|    |       |      |   \
|      |   |  |    |  |____    |      |    |   _   |____  |___/
|      |   |  |    |  |        |      |    |    |  |      |  \
|____  |___|  |___/   |____    |    __|__  |____|  |____  |   \
 
*/

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