Submission #1147580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147580		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;
const int LG = 20;
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 = dis(x, y);
    // for(int j = 0 ; j < k.size() ; j++) {
    //   a = min(a, dis(x, k[j]) + dis((k[j]+n)%(2*n), y) + 1);
    // }
    
    int r = 0;
    for(int i = LG ; i >= 0 ; i--) if(r + (1LL << i) < k.size() and k[r + (1LL << i)] <= x) r += (1LL << i);
    if(k[0] <= x) a = min(a, dis(x, k[r]) + dis((k[r]+n)%(2*n), y) + 1);
    if(r+1 < k.size()) a = min(a, dis(x, k[r+1]) + dis((k[r+1]+n)%(2*n), y) + 1);
    else a = min(a, dis(x, k[0]) + dis((k[0]+n)%(2*n), y) + 1);
    cout << a << '\n';
  }
}

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