제출 #1172723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172723		Nomio	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	52 ms	8600 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n;
	int m, q;
	cin >> n >> m >> q;
	vector<ll> v, vec;
	for(int i = 0; i < m; i++) {
		int a;
		cin >> a;
		v.push_back(a);
		vec.push_back(a + n);
	}
	sort(v.begin(), v.end());
	sort(vec.begin(), vec.end());
//	for(int x : v) {
//		cout << x << ' ';
//	}
//	cout << '\n';
//	for(int x : vec) {
//		cout << x << ' ';
//	}
//	cout << '\n';
	while(q--) {
		int x, y;
		cin >> x >> y;
		if(x > y) swap(x, y);
		ll ans1 = y - x;
		ll ans2 = n * 2 - ans1;
		ll ans = 1e10;
		ans = min({ans, ans1, ans2});
		ll ans3 = 0, ans4 = 0, ans5 = 0, ans6 = 0, ans7 = 0, ans8 = 0, ans9 = 0, ans10 = 0, ans11 = 0, ans12 = 0;
		if(v.back() >= x) {
			int id1 = *lower_bound(v.begin(), v.end(), x);
			ans3 += (id1 - x) + 1;
			ans4 += (id1 - x) + 1;
			id1 += n;
			ans3 += abs(y - id1);
			ans4 += (n * 2 - abs(y - id1)); 
			ans = min({ans, ans3, ans4});
		}
		if(v[0] <= x) {
			int id2 = *--upper_bound(v.begin(), v.end(), x);
			ans5 += abs(id2 - x) + 1;
			ans6 += abs(id2 - x) + 1;
			id2 += n;
			ans5 += abs(y - id2);
			ans6 += (n * 2 - abs(y - id2));
			ans = min({ans, ans5, ans6});
		}
		if(vec.back() >= x) {
			int id1 = *lower_bound(vec.begin(), vec.end(), x);
			ans7 += (id1 - x) + 1;
			ans8 += (id1 - x) + 1;
			id1 -= n;
			ans7 += abs(y - id1);
			ans8 += (n * 2 - abs(y - id1)); 
			ans = min({ans, ans7, ans8});
		}
		if(vec[0] <= x) {
			int id2 = *--upper_bound(vec.begin(), vec.end(), x);
			ans9 += abs(id2 - x) + 1;
			ans10 += abs(id2 - x) + 1;
			id2 -= n;
			ans9 += abs(y - id2);
			ans10 += (n * 2 - abs(y - id2));
			ans = min({ans, ans9, ans10});
		}
		int id = vec.back();
		ans11 = abs(id - x) + 1;
		ans12 = n * 2 - ans11 + 2;
		id -= n;
//		cout << ans11 << ' ' << ans12 << '\n';
//		cout << id << '\n';
		ans = min({ans, ans11 + abs(id - y), ans11 + n * 2 - abs(id - y), ans12 + abs(id - y), ans12 + n * 2 - abs(id - y)});
		cout << ans << '\n';
	}
	return 0;
}

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