Submission #1058573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058573		Gray	Circle Passing (EGOI24_circlepassing)	C++17	100 / 100	72 ms	13396 KiB

Main

// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <bitset>
#include <cassert>
#include <functional>
#include <map>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#define ll long long
#define ull unsigned ll
#define ld long double
#define ln "\n"
#define ff first
#define ss second
using namespace std;
const ll inf=2e18;
const ll MOD = 1000000007;
ll dist(ll x, ll y, ll n){
	return min(abs(x-y), 2*n-abs(x-y));
}
void solve(){
	ll n, m, q; cin >> n >> m >> q;
	vector<ll> a(2*m);
	for (ll i=0; i<m; i++){
		cin >> a[i*2];
		a[i*2+1]=a[i*2]+n;
	}
	sort(a.begin(), a.end());
	while (q--){
		ll u, v; cin >> u >> v;
		ll nind = lower_bound(a.begin(), a.end(), u)-a.begin();
		nind%=2*m;
		ll pind = (nind-1+2*m)%(2*m);
		cout << min(dist(u, v, n), min(1+dist(u, a[nind], n)+dist((a[nind]+n)%(2*n),v, n), 1+dist(u, a[pind], n)+dist((a[pind]+n)%(2*n), v, n))) << ln;
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	ll t=1;
	// cin >> t;
	while (t--) solve();
}

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