Submission #1171521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171521		uranhishig	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	183 ms	8664 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pb push_back
#define int long long
#define ff first
#define ss second
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)

int n, m, t;

int f(int x, int y) {
	int c1 = max(x, y) - min(x, y);
	int c2 = 2 * n - c1;
	int z = min(c1, c2);
	return z;
}

signed main() {
	cin >> n >> m >> t;
	vector<int> v;
	for (int i = 0; i < m; i++) {
		int x;	cin >> x;
		v.pb(x);v.pb(x + n);
	}
	v.push_back(INT_MAX);
	sort(v.begin(), v.end());
	while (t--) {
		int ans = 1e9;
		int x, y;	
		cin >> x>> y;
		int t = *lower_bound(v.begin(), v.end(), x);
		auto tt = lower_bound(v.begin(), v.end(), x) ;
		if (tt != v.begin()) {
			tt--;
			int e;
			if(*tt < n) e= *tt+n;
			else e= *tt-n;
			ans = min({ ans, f(x, y), f(x, *tt) + f(e, y)+1 } );
		}
		if (t != INT_MAX) {
			int e;
			if(t < n) e= t+n;
			else e= t-n;
			ans = min( { ans, f(x, y), f(x, t) + f(e, y)+1});
		}
		swap(x,y);
		 t = *lower_bound(v.begin(), v.end(), x);
		tt = lower_bound(v.begin(), v.end(), x) ;
		if (tt != v.begin()) {
			tt--;
			int e;
			if(*tt < n) e= *tt+n;
			else e= *tt-n;
			ans = min({ ans, f(x, y), f(x, *tt) + f(e, y)+1 } );
		}
		if (t != INT_MAX) {
			int e;
			if(t < n) e= t+n;
			else e= t-n;
			ans = min( { ans, f(x, y), f(x, t) + f(e, y)+1});
		}
		
		cout << ans << endl;
//		cout << min(ans1, ans) << "\n";
	}
	return 0; 
}

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