| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1099351 | Zflop | Circle Passing (EGOI24_circlepassing) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 int ll
#define pb push_back
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);
bestfriend.pb(b + N);
}
auto Do = [&] (int a,int b) {
if (a > 2 * N)
a -= 2 * N;
if (a > b)
swap(a,b);
int ans = (int)1e9;
ans = b - a;
ans = min(ans,a + 2 * N - b);
return ans;
};
while(Q--) {
int a,b; cin >> a >> b;
if (a > b)
swap(a,b);
int ans = (int)1e9;
ans = b - a;
ans = min(ans,a + 2 * N - b);
int l = 1,r = bestfriend.size() - 1;
int p = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (bestfriend[mid] <= a) {
p = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
ans = min({ans,Do(bestfriend[p],b) + a - bestfriend[p],Do(bestfriend[p + 1]) + bestfriend[p + 1] - a});
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();
}