Submission #1044134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044134		vjudge1	Circle Passing (EGOI24_circlepassing)	C++17	100 / 100	73 ms	13696 KiB

Main

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

#define int long long
#define ar array
#define ld long double

const int N = 3e5 + 20;
const int MOD = 1e9 + 7;
const int INF = 1e10;

int n;

int dist(int a,int b){
	return min(abs(a - b), 2 * n - abs(a - b));
}

int dist(int a,int b,ar<int, 2> c){
	return 1 + min(dist(a, c[0]) + dist(b, c[1]), dist(a, c[1]) + dist(b, c[0]));
}

signed main(){ios::sync_with_stdio(false);cin.tie(0);	
	int m, q;
	cin>>n>>m>>q;
	vector<int> v;
	while(m--){
		int x;
		cin>>x;
		v.push_back(x);
		v.push_back(n + x);
	}
	sort(v.begin(), v.end());
	while(q--){
		int a, b;
		cin>>a>>b;
		vector<ar<int, 2> > s;
		int ans = dist(a, b);
		auto it = lower_bound(v.begin(), v.end(), a);
		if(it != v.end())s.push_back({*it, (*it + n ) % (2*n)});
		if(it != v.begin()){
			--it;
			s.push_back({*it, (*it + n ) % (2*n)});
		}
		it = lower_bound(v.begin(), v.end(), b);
		if(it != v.end())s.push_back({*it, (*it + n ) % (2*n)});
		if(it != v.begin()){
			--it;
			s.push_back({*it, (*it + n ) % (2*n)});
		}
		for(auto r: s)ans = min(ans, dist(a, b, r));
		cout<<ans<<'\n';
	}
}

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