제출 #1151476

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151476		ghammazhassan	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	352 ms	79488 KiB

Main

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define int long long
const int N=2e5+5;
const int M=998244353;
const int LOG = 18;
int n , m , c , t=1 , q=1 , x , y , p[N];
vector<int>a;
int que(int x,int y){
	if (x>y){
		swap(x,y);
	}
	int l=0;
	int h=m*2-1;
	int mi=(l+h+1)/2;
	while (l<h){
		if (a[mi]>x){
			h=mi-1;
		}
		else{
			l=mi;
		}
		mi=(l+h+1)/2;
	}
	int u1=a[mi];
	l=0;
	h=m*2-1;
	mi=(l+h)/2;
	while (l<h){
		if (a[mi]<x){
			l=mi+1;;
		}
		else{
			h=mi;
		}
		mi=(l+h)/2;
	}
	int u2=a[mi];
	int d1=min(y-x,x+2*n-y);
	int d2=abs(u1-x)+abs(u1+n-y)+1;
	int d3=abs(u2-x)+abs(u2+n-y)+1;
	return min({d1,d2,d3});
}
void solve()
{
	cin >> n >> m >> q;
	map<int,int>d;
	for (int i=0;i<m;i++){
		cin >> x;
		d[x]=1;
		d[x+n]=1;
		a.push_back(x);
	}
	for (int i=0;i<3*m;i++){
		a.push_back(a[i]+n);
	}
	for (int o=0;o<q;o++){
		cin >> x >> y;
		cout << min(que(x,y),que(x+n,y+n)) << endl;
	}
}
signed main()
{

    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed<<setprecision(9);
    // int t=1;
    // cin >> t;
    
    for (int _=1;_<=t;_++){
    	solve();
    	q++;
    }
}

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