Submission #1278158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278158		SSKMF	Circle Passing (EGOI24_circlepassing)	C++20	100 / 100	48 ms	4544 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int lungime , numar_muchii , capat[1000001];

inline int Distanta (const int nod_1 , const int nod_2)
{
    return min(abs(nod_1 - nod_2) , 2 * lungime - abs(nod_1 - nod_2));
}

inline int Next (const int minim)
{
    int stanga = 1 , dreapta = numar_muchii;
    while (stanga <= dreapta)
    {
        const int mijloc = (stanga + dreapta) >> 1;
        if (capat[mijloc] < minim) { stanga = mijloc + 1; }
        else { dreapta = mijloc - 1; }
    }

    return stanga <= numar_muchii ? stanga : 1;
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int numar_intrebari;
    cin >> lungime >> numar_muchii >> numar_intrebari;

    for (int indice = 1 ; indice <= numar_muchii ; indice++)
        { cin >> capat[indice]; }

    for (int indice = numar_muchii + 1 ; indice <= 2 * numar_muchii ; indice++)
        { capat[indice] = capat[indice - numar_muchii] + lungime; }

    numar_muchii <<= 1;
    while (numar_intrebari--)
    {
        int inceput , sfarsit;
        cin >> inceput >> sfarsit;

        int rezultat = Distanta(inceput , sfarsit) , locatie = Next(inceput);
        
        rezultat = min(rezultat , Distanta(inceput , capat[locatie]) + 1 + Distanta((capat[locatie] + lungime) % (2 * lungime) , sfarsit));

        if (locatie != 1) { locatie--; }
        else { locatie = numar_muchii; }

        rezultat = min(rezultat , Distanta(inceput , capat[locatie]) + 1 + Distanta((capat[locatie] + lungime) % (2 * lungime) , sfarsit));

        cout << rezultat << '\n';
    }
    
    return 0;
}

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