Submission #1097262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097262		Trisanu_Das	Circle Passing (EGOI24_circlepassing)	C++17	100 / 100	264 ms	52680 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  
  int n, m, q;
  cin >> n >> m >> q;
  
  set<int> s;
  for (int i = 0; i < m; ++i) {
    int x;
    cin >> x;
    s.emplace(x);
    s.emplace(x + n);
  }
  
  auto mod = [&](int x) { return (x % (2 * n) + 2 * n) % (2 * n); };
  auto dist = [&](int x, int y) { return min(mod(x - y), mod(y - x)); };
  
  for (int i = 0; i < q; ++i) {
    int x, y;
    cin >> x >> y;
    int ans = dist(x, y);
    if (m) {
      auto it = s.lower_bound(x);
      if (it == end(s)) it = begin(s);
      ans = min(ans, dist(x, *it) + 1 + dist(mod(*it + n), y));
      
      it = prev(it == begin(s) ? end(s) : it);
      ans = min(ans, dist(x, *it) + 1 + dist(mod(*it + n), y));
    }
    
    cout << ans << '\n';
  }
}

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