Submission #1115728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115728		ahoraSoyPeor	Circle Passing (EGOI24_circlepassing)	C++14	100 / 100	95 ms	9904 KiB

Main

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

#define ff first
#define ss second
#define pb push_back

typedef long long ll;
typedef pair <int,int> pii;

int N, M, Q;
vector <int> bff;

int get_bff ( int x ) {
    return (x+N) % (2*N);
}

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

bool check_bff ( int a, int b ) {
    auto pnt_a = lower_bound ( bff.begin(), bff.end(), a ),
        pnt_b = upper_bound ( bff.begin(), bff.end(), b );
    if ( a <= b )
        return pnt_b - pnt_a > 0;
    return pnt_a != bff.end() or pnt_b != bff.begin();
}

int nxt_bff ( int x ) {
    auto pnt_x = lower_bound ( bff.begin(), bff.end(), x );
    if ( pnt_x != bff.end() )
        return *pnt_x;
    return bff[0];
}

int bef_bff ( int x ) {
    auto pnt_x = lower_bound ( bff.begin(), bff.end(), x );
    if ( pnt_x != bff.begin() )
        return *(--pnt_x);
    return bff.back ();
}

int get_ans ( int x_i, int y_i ) {
    int nxt = nxt_bff ( x_i ), bef = bef_bff ( x_i );
    int res = min ({ dist ( x_i, y_i ), 
                dist ( x_i, nxt ) + 1 + dist ( get_bff (nxt), y_i ) ,
                dist ( x_i, bef ) + 1 + dist ( get_bff (bef), y_i )}); 
    return res;
}

int main () {
        
    #ifndef LOCAL
    #endif

    scanf ( "%d%d%d", &N, &M, &Q );
    while ( M-- ) {
        int curr_bff;
        scanf ( "%d", &curr_bff );
        bff.pb ( curr_bff ), bff.pb ( curr_bff + N );
    }
    sort ( bff.begin(), bff.end() );

    while ( Q-- ) {
        int x_i, y_i;
        scanf ( "%d%d", &x_i, &y_i );
        printf ( "%d\n", get_ans ( x_i, y_i ) );
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:57:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf ( "%d%d%d", &N, &M, &Q );
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:60:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf ( "%d", &curr_bff );
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:67:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf ( "%d%d", &x_i, &y_i );
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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