Submission #1098340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098340		ALTAKEXE	Circle Passing (EGOI24_circlepassing)	C++17	20 / 100	39 ms	63828 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 best[4000002], r[4000002], l[4000002];
ll n, m, q;
ll dist(ll a, ll b)
{
  return min(abs(a - b), 2 * n - abs(a - b));
}
int main()
{
  cin >> n >> m >> q;
  for (ll i = 0; i < n * 2; i++)
    best[i] = 0;
  for (ll i = 0; i < m; i++)
  {
    ll x;
    cin >> x;
    best[x] = best[x + n] = 1;
  }
  ll po = -1;
  for (ll i = 0; i < n * 3; i++)
  {
    if (best[i % (n * 2)])
      po = i % (n * 2);
    l[i % (n * 2)] = po;
  }
  po = -1;
  for (ll i = n * 3 - 1; i >= 0; i--)
  {
    if (best[i % (n * 2)])
      po = i % (n * 2);
    r[i % (n * 2)] = po;
  }
  while (q--)
  {
    ll a, b;
    cin >> a >> b;
    if (a > b)
      swap(a, b);
    ll m1 = dist(a, b);
    ll m2 = l[a] == -1 ? 1e9 : dist(a, l[a]) + dist((l[a] + n) % (n * 2), b) + 1;
    ll m3 = r[a] == -1 ? 1e9 : dist(a, r[a]) + dist((r[a] + n) % (n * 2), b) + 1;
    // cout << m1 << " " << m2 << " " << m3 << " " << left[a] << " " << right[a] << " m\n";
    cout << min(min(m1, m2), m3) << "\n";
  }
  return 0;
}

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