Queries to check if it is possible to join boxes in a circle | Python 3 implementation of above approach ; Print the answer to each query ; setting the flag for exception ; replacing the greater element in i and j ; checking if that box is not used in previous query . ; checking if connecting to the same box ; case 1 : x < i and y lies between i and j ; case 2 : x lies between i and j and y > j ; if flag is not reset inbetween . ; Driver code
MAX = 50 NEW_LINE def solveQuery ( n , q , qi , qj ) : NEW_LINE INDENT arr = [ None ] * MAX NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT arr [ i ] = 0 NEW_LINE DEDENT for k in range ( q ) : NEW_LINE INDENT flag = 0 NEW_LINE if ( qj [ k ] < qi [ k ] ) : NEW_LINE INDENT qj [ k ] , qi [ k ] = qi [ k ] , qj [ k ] NEW_LINE DEDENT if ( arr [ qi [ k ] ] != 0 or arr [ qj [ k ] ] != 0 ) : NEW_LINE INDENT flag = 1 NEW_LINE DEDENT elif ( qi [ k ] == qj [ k ] ) : NEW_LINE INDENT flag = 1 NEW_LINE DEDENT else : NEW_LINE INDENT for i in range ( 1 , qi [ k ] ) : NEW_LINE INDENT if ( arr [ i ] != 0 and arr [ i ] < qj [ k ] and qi [ k ] < arr [ i ] ) : NEW_LINE INDENT flag = 1 NEW_LINE break NEW_LINE DEDENT DEDENT if ( flag == 0 ) : NEW_LINE INDENT for i in range ( qi [ k ] + 1 , qj [ k ] ) : NEW_LINE INDENT if ( arr [ i ] != 0 and arr [ i ] > qj [ k ] ) : NEW_LINE INDENT flag = 1 NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT DEDENT if ( flag == 0 ) : NEW_LINE INDENT print ( " YES " ) NEW_LINE arr [ qi [ k ] ] = qj [ k ] NEW_LINE arr [ qj [ k ] ] = qi [ k ] NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 10 NEW_LINE q = 7 NEW_LINE qi = [ 1 , 2 , 2 , 2 , 9 , 10 , 8 ] NEW_LINE qj = [ 5 , 7 , 3 , 4 , 9 , 9 , 6 ] NEW_LINE solveQuery ( n , q , qi , qj ) NEW_LINE DEDENT