Submission #1232715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232715		coco2311	Circle Passing (EGOI24_circlepassing)	C++17	100 / 100	569 ms	94524 KiB

Main

#include <iostream>
#include <set>
#include <cmath>
using namespace std;


int N;

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

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//    freopen("input.in","r",stdin);
    int M,Q; cin>>N>>M>>Q;
    set<int> l;
    int a;
    for(int i=0;i<M;i++){
        cin>>a;
        l.insert(a);
        l.insert(a+N);
        l.insert(a+2*N);
        l.insert(a-N);
    }
    int x,y;
    int minPassesXY,w,minPassesXami1,minPassesYami1,minPassesXami2,minPassesYami2;
    int ami[2]; // amitie

    for(int i=0;i<Q;i++){
        cin>>x>>y;
        minPassesXY=dist(x,y);
        ami[0]=(*l.lower_bound(x)+2*N)%(2*N);
        auto it=l.upper_bound(x);
        it--;
        ami[1]=((*it)+2*N)%(2*N);
        for(int j=0;j<2;j++){
            minPassesXami1=dist(x,ami[j]);

            minPassesYami2=dist(y,(ami[j]+N)%(2*N));

            minPassesXY=min(minPassesXY,minPassesYami2+minPassesXami1+1);

            minPassesYami1=dist(y,ami[j]);

            minPassesXami2=dist(x,(ami[j]+N)%(2*N));

            minPassesXY=min(minPassesXY,minPassesXami2+minPassesYami1+1);
        }
        cout<<minPassesXY<<'\n';
    }
} 

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