Submission #1098339

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