Submission #1168321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168321		pyrros	Circle Passing (EGOI24_circlepassing)	C++20	0 / 100	2095 ms	469480 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define int long long

signed main()
{
	int n, me, q;
	cin>>n>>me>>q;
	vector<int> bff;
	int pivot = 0;
	map<int, bool> m;
	for(int i = 0; i < me; i++)
	{
		int a; cin>>a;
		bff.push_back(a);
		m[a] = 1;
		m[a+n] = 1;
	}
	//st1
	//int diff = pivot;
	int new_target = 0;
	while(q--)
	{
		int x, y; cin>>x>>y;
		pivot = x;
		if(y > x){
		new_target = y-pivot;
	}else if(y < x)
	{
		new_target = 2*n-(x-y);
	}
	//cout<<"new_target: "<<new_target<<endl;
	int answer = 1e9;
	//asume x = 0 and pivot;
	//approach from centre
	int perimeter = n/2+1;
	//new target is the y after shifted
	//go left first
	//cout<<"p: "<<perimeter<<endl;
	//cout<<"from left to right: "<<endl;
	for(int j = 0; j <= perimeter; j++)
	{
		//cout<<"nope"<<endl;
		if(m[j+pivot] == 1) //exist a shorter path
		{
			answer = min(answer, j+(abs((j+n)-new_target))+1);
			//cout<<"real ans: "<<j+(abs((j+n)-new_target))+1<<endl;
			//cout<<"j: "<<j<<" "<<"answer: "<<answer<<endl;
		}
	}
	//cout<<endl;
	//cout<<"from right to left: "<<endl;
	//to the right where start 2n-1;
	for(int j = 1; j <= perimeter; j++)
	{
		int new_idx = 2*n-new_target;
		int ref = new_idx;
		//cout<<"newidx: "<<new_idx<<" "<<"new_target: "<<new_target<<endl;
		ref = (x+new_target)%2*n;
		//cout<<"ref: "<<ref<<endl;
		if(m[ref] == 1) //shows that got exist from the left hemisphere;
		{
			answer = min(answer, j+abs((n-j) - new_target)+1);
			//cout<<"real ans: "<<j+abs((n-j) - new_target)+1<<endl;
		}
		
		//cout<<"j: "<<j<<" "<<"answer: "<<answer<<endl;
	}
	
	
	//last segment to decide and compare if it is better to not use any bridge
	if(new_target < n)
	{
			answer = min(answer, new_target);
	}
	else if(new_target > n)
	{
		answer = min(answer, 2*n-new_target);
	}else if(new_target == n)
	{
		answer = min(answer, n);
	}
	/*
	int center = abs(n-new_target);
	int start;
	if(new_target > n)
	{
		start = 2*n-new_target;
	}
	else if(new_target < n)
	{
		start = new_target;
	}
	else if(new_target == n)
	{ cout<<1<<'\n'; continue;
	}
	answer = min(start, center+1);
	cout<<answer<<'\n';
	*/
	cout<<answer<<'\n';
	//cout<<endl;
	//cout<<endl;
	}
	
}

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