Submission #1058260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058260		SzymonKrzywda	Circle Passing (EGOI24_circlepassing)	C++17	100 / 100	187 ms	6596 KiB

Main

#include <bits/stdc++.h>

using namespace std;
int n;

int odl(int a, int b){
    int wynik=abs(a-b);
    wynik = min(wynik, (2*n)-max(a,b)+min(a,b));
    return wynik;
}

int main()
{
    int m,q,a,b;
    cin >> n >> m >> q;
    vector<int> pary(0);
    
    for (int i=0; i<m; i++){
        cin >> a;
        pary.push_back(a);
        pary.push_back(a+n);
        
    }

    sort(pary.begin(),pary.end());

/*
    //for (auto [i_1,i_2] : pary) cout << i_1 << " " << i_2 << endl;
    //liczymy pierwszy na lewo
    int akt_para = 1;
    int akt_idx = pary[0];
    
    vector<int> lewo(2*n);
    
    for (int i=0; i<2*n; i++){
        if (akt_para < pary.size() && pary[akt_para]==akt_idx){
            akt_para++;
        }
        //cout << akt_idx << endl;
        lewo[akt_idx] = pary[akt_para-1];
        cout << akt_idx << " " << lewo[akt_idx] << endl;
        akt_idx = (akt_idx+1)%(2*n);

    }

    //Liczymy pierwszy na prawo
    akt_para = (2*m)-2;
    akt_idx = pary[(2*m)-1];
    
    vector<int> prawo(2*n);

    for (int i=0; i<2*n; i++){
        //cout << "DUPA " << (akt_idx-1+(2*n))%(2*n) << " " << akt_idx <<  endl;
        if (akt_para >=0 && pary[akt_para]==akt_idx){
            akt_para--;
        }
        prawo[akt_idx] = pary[akt_para+1];
        cout << akt_idx << " " << prawo[akt_idx] << endl;
        akt_idx = (akt_idx-1+(2*n))%(2*n);
    }*/



    for (int i=0; i<q; i++){
        
                
        cin >> a >> b;
        int lewo,prawo;
        //prawo
        
        int lewo_=0,prawo_=(2*m)-1;
        while (lewo_<prawo_){
            int mid = (lewo_+prawo_)/2;
            //cout << lewo_ << " " << prawo_ << " " << mid << endl;
            if (pary[mid]>=a) prawo_=mid;
            else lewo_ = mid+1;
        }
        
        if (pary[lewo_]>=a) prawo = pary[lewo_];
        else prawo = pary[0];
        
        
        
        //lewo
        
        lewo_=0,prawo_=(2*m)-1;
        while (lewo_<prawo_){
            int mid = (lewo_+prawo_+1)/2;
            //cout << "TU: " << lewo_ << " " << prawo_ << " " << mid << endl;
            if (pary[mid]<=a) lewo_=mid;
            else prawo_ = mid-1;
        }
        //cout << pary[lewo_] << " " << lewo_ << endl;
        if (pary[lewo_]<=a) lewo = pary[lewo_];
        else lewo = pary[(2*m)-1];
        
        
        //cout << a << " " << b<< " " << lewo << " " << prawo << endl;

        
        int wynik = odl(a,b);
        wynik = min(wynik, 1+odl(a,prawo) + odl(((prawo+n)%(2*n)), b));
        wynik = min(wynik, 1+odl(a,lewo) + odl(((lewo+n)%(2*n)), b));
        cout << wynik << endl;
    }
    return 0;
}

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