Submission #1151497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151497		KaleemRazaSyed	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	136 ms	4316 KiB

Main

#include<bits/stdc++.h>

using namespace std;


int n, m, q;

int dist(int x, int y)
{
  if(x < y) swap(x, y);
  return min(2 * n - (x - y), x - y);
}

int dist2(int x, int y, int k1, int k2) {
  return min(dist(x, k1) + dist(k2, y), dist(x, k2) + dist(k1, y)) + 1;
}
int main()
{
  cin >> n >> m >> q;

  int k[2 * m];

  for(int i = 0; i < m; i ++)
    cin >> k[i];

  for(int i = 0; i < m; i ++)
    k[i + m] = k[i] + n;
  
  while(q--)
    {
      int x, y;
      cin >> x >> y;
      int ans = dist(x, y);
      if(x > y) swap(x, y);
      // x <= y
      ans = min(ans, dist2(x, y, k[m - 1], k[m - 1] + n));
      ans = min(ans, dist2(x, y, k[0], k[0] + n));
      auto it = lower_bound(k, k + 2 * m, x);
      if(it != k + 2 * m)
	{
	  int idx = it - k;
	  ans = min(ans, dist2(x, y, k[idx], (k[idx] + n) % (2 * n)));
	}
      if(it != k)
	{
	  it--;
	  int idx = it - k;
	  ans = min(ans, dist2(x, y, k[idx], (k[idx] + n) % (2*n)));
	}
      cout << ans << endl;
    }

  
  return 0;
}

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