Submission #1098346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098346		ALTAKEXE	Circle Passing (EGOI24_circlepassing)	C++17	100 / 100	367 ms	52564 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define inf INT_MAX
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FAR(i, a, b) for (int i = (a); i >= (b); i--)
#define all(x) (x.begin(), x.end())
const int MOD = 1e9 + 7;
using namespace std;
ll n, m, q;
ll dist(ll a, ll b)
{
  return min(abs(a - b), 2 * n - abs(a - b));
}
int main()
{
  set<int> best;
  cin >> n >> m >> q;
  for (ll i = 0; i < m; i++)
  {
    ll x;
    cin >> x;
    best.insert(x);
    best.insert(x + n);
  }
  while (q--)
  {
    ll a, b;
    cin >> a >> b;
    if (a > b)
      swap(a, b);
    int l = -1;
    int r = -1;
    auto it1 = best.upper_bound(a);
    if (it1 != best.begin())
    {
      it1--;
      l = (*it1) % (n * 2);
    }
    else
    {
      it1 = best.end();
      it1--;
      l = (*it1) % (n * 2);
    }
    it1 = best.lower_bound(a);
    if (it1 != best.end())
    {
      r = (*it1) % (n * 2);
    }
    else
    {
      it1 = best.begin();
      r = (*it1) % (n * 2);
    }
    ll m1 = dist(a, b);
    ll m2 = l == -1 ? 1e9 : dist(a, l) + dist((l + n) % (n * 2), b) + 1;
    ll m3 = r == -1 ? 1e9 : dist(a, r) + dist((r + n) % (n * 2), b) + 1;
    cout << min(min(m1, m2), m3) << "\n";
  }
  return 0;
}

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