Submission #1241358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241358		aren_dance	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	158 ms	2372 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N=6e5;
int n,m,q;
vector<int> k;
int path(int u,int v){
    if(u>v){
        swap(u,v);
    }
    return min(v-u,u+2*n-v);
}
int pat(int u,int v,int i){
    if(i>=m || i<0){
        return 1e9;
    }
    return min(1+path(u,k[i])+path(n+k[i],v),1+path(u,n+k[i])+path(v,k[i])); 
}
int main()
{
    cin>>n>>m>>q;
    k.resize(m);
    for(int i=0;i<m;++i){
        cin>>k[i];
    }
    sort(k.begin(),k.end());
    while(q--){
        int u,v;
        cin>>u>>v;
        if(u>v){
            swap(u,v);
        }
        int answ=path(u,v);
        answ=min(answ,pat(u,v,0));
        answ=min(answ,pat(u,v,m-1));
        int id=lower_bound(k.begin(),k.end(),u)-k.begin();
        answ=min(answ,pat(u,v,id));
        answ=min(answ,pat(u,v,id-1));
        cout<<answ<<'\n';
    }
    return 0;
}

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