Submission #1058123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058123		SzymonKrzywda	Circle Passing (EGOI24_circlepassing)	C++17	42 / 100	430 ms	1048580 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 wynik = odl(a,b);
        wynik = min(wynik, 1+odl(a,prawo[a]) + odl(((prawo[a]+n)%(2*n)), b));
        wynik = min(wynik, 1+odl(a,lewo[a]) + odl(((lewo[a]+n)%(2*n)), b));
        cout << wynik << endl;
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         if (akt_para < pary.size() && pary[akt_para]==akt_idx){
      |             ~~~~~~~~~^~~~~~~~~~~~~

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