Submission #1147520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147520		orzdraiduwu	Circle Passing (EGOI24_circlepassing)	C++20	14 / 100	109 ms	5972 KiB

Main

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

int n, m, q;
int dis(int x, int y) { return min(abs(x-y), 2*n - abs(x-y)); }
signed main() {
  cin >> n >> m >> q;
  vector<int> k(m);
  for(int i = 0 ; i < m ; i++) {
    cin >> k[i];
    k.push_back(k[i] + n);
  }

  sort(k.begin(), k.end());
  for(int i = 0 ; i < q ; i++) {
    int x, y; cin >> x >> y;
    // int a = min(abs(x-y), abs(min(x, y)) + abs(y-2*n));
    int a = dis(x, y);
    int l = 0, r = k.size();
    while(r - l > 1) {
      int md = (l+r)/2;
      if(k[md] >= x) r = md;
      else l = md;
    }

    // else {
    //   l = 
    // }

    int w = k[l];
    int b = dis(x, w);
    w += n;
    w %= 2*n;
    b += dis(w, y);
    int e = k[r];
    int c = dis(x, e);
    e += n;
    e %= 2*n;
    c += dis(e, y);
    b++; c++;
    // cout << endl;
    // cout << a << " " << b << " " << c << endl;
    cout << min({a, b, c}) << endl;
  }
}

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