Submission #1099362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099362		Zflop	Circle Passing (EGOI24_circlepassing)	C++14	31 / 100	195 ms	8692 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
#define sor(x) sort(all(x))
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define int ll
int N,M,Q;
void solve() {
    cin >> N >> M >> Q;
    vi bestfriend{0};
    for (int i = 0; i < M;++i) {
        int b = 0;
        cin >> b;
        bestfriend.pb(b + 1);
        bestfriend.pb(b + N + 1);
        }

    auto Do = [&] (int a,int b) {
        if (a > 2 * N)
            a -= 2 * N;
        if (a > b)
            swap(a,b);
        int ans = (int)1e12;
        ans = b - a;
        ans = min(ans,a + 2 * N - b);
        return ans;
    };
    sor(bestfriend);
    while(Q--) {
        int a,b; cin >> a >> b;
        ++a,++b;
        if (a > b)
            swap(a,b);
        int ans = (int)1e12;
        ans = b - a;
        ans = min(ans,a + 2 * N - b);
        if(bestfriend.size() == 1) {
            cout << ans << '\n';
            continue;
        }
        int l = 1,r = bestfriend.size() - 1;
        int p = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            //cout << mid << ' ' << bestfriend[mid] << '\n';
            if (bestfriend[mid] <= a) {
                p = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if(p == -1) {
            ans = min(ans,Do(bestfriend.back() - N,b) + a + 1 + 2 * N - bestfriend.back());
            ans = min(ans,Do(bestfriend[1] + N,b) + bestfriend[1] - a + 1);
        }
        if(p != -1){
            ans = min(ans,Do(N + bestfriend[p],b) + a - bestfriend[p] + 1);
            ans = min(ans,Do(N + bestfriend[p + 1],b) + bestfriend[p + 1] - a + 1);
        }
        cout << ans << "\n";
    }
}

main(){
    solve();
}

Compilation message (stderr)

Main.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main(){
      | ^~~~

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