

'''simple docstring'''

def 					__UpperCamelCase				(						):






     '''simple docstring'''





     return [list(range(10_00 - i,       -10_00 - i,       -1			)			) for i in range(10_00			)]


UpperCAmelCase					 =	generate_large_matrix()
UpperCAmelCase					 =	(
    [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]],
    [[3, 2], [1, 0]],
    [[7, 7, 6]],
    [[7, 7, 6], [-1, -2, -3]],
    grid,
)

def 					__UpperCamelCase				(						lowercase__    :	list[list[int]]			):






     '''simple docstring'''





     assert all(row == sorted(lowercase__,       reverse=lowercase__			) for row in grid			)
     assert all(list(lowercase__			) == sorted(lowercase__,       reverse=lowercase__			) for col in zip(*lowercase__			)			)

def 					__UpperCamelCase				(						lowercase__    :	list[int]			):






     '''simple docstring'''





     __lowercase      		=0
     __lowercase      		=len(lowercase__			) - 1

     # Edge cases such as no values or all numbers are negative.
     if not array or array[0] < 0:
          return 0

     while right + 1 > left:
          __lowercase      		=(left + right) // 2
          __lowercase      		=array[mid]

          # Num must be negative and the index must be greater than or equal to 0.
          if num < 0 and array[mid - 1] >= 0:
               return mid

          if num >= 0:
               __lowercase      		=mid + 1
          else:
               __lowercase      		=mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
     return len(lowercase__			)

def 					__UpperCamelCase				(						lowercase__    :	list[list[int]]			):






     '''simple docstring'''





     __lowercase      		=0
     __lowercase      		=len(grid[0]			)

     for i in range(len(lowercase__			)			):
          __lowercase      		=find_negative_index(grid[i][:bound]			)
          total += bound
     return (len(lowercase__			) * len(grid[0]			)) - total

def 					__UpperCamelCase				(						lowercase__    :	list[list[int]]			):






     '''simple docstring'''





     return len([number for row in grid for number in row if number < 0]			)

def 					__UpperCamelCase				(						lowercase__    :	list[list[int]]			):






     '''simple docstring'''





     __lowercase      		=0
     for row in grid:
          for i, number in enumerate(lowercase__			):
               if number < 0:
                    total += len(lowercase__			) - i
                    break
     return total

def 					__UpperCamelCase				(						):






     '''simple docstring'''





     from timeit import timeit

     print('Running benchmarks'			)
     __lowercase      		=(
         'from __main__ import count_negatives_binary_search, '
         'count_negatives_brute_force, count_negatives_brute_force_with_break, grid'
     )
     for func in (
         "count_negatives_binary_search",  # took 0.7727 seconds
         "count_negatives_brute_force_with_break",  # took 4.6505 seconds
         "count_negatives_brute_force",  # took 12.8160 seconds
     ):
          __lowercase      		=timeit(F'''{func}(grid=grid)''',       setup=lowercase__,       number=5_00			)
          print(F'''{func}() took {time:0.4f} seconds'''			)


if __name__ == "__main__":
       import doctest

       doctest.testmod()
       benchmark()





'''simple docstring'''

import unittest

import numpy as np
import torch

from diffusers import PNDMPipeline, PNDMScheduler, UNetaDModel
from diffusers.utils.testing_utils import enable_full_determinism, require_torch, slow, torch_device


enable_full_determinism()


class 	lowerCAmelCase  (   unittest.TestCase ):







       @property
       def       snake_case (				self      :			str   ):







            """simple docstring"""







            torch.manual_seed(0   )
            __lowercase      		=UNetaDModel(
                block_out_channels=(32, 64)    ,   layers_per_block=2    ,   sample_size=32    ,   in_channels=3    ,   out_channels=3    ,   down_block_types=('DownBlock2D', 'AttnDownBlock2D')    ,   up_block_types=('AttnUpBlock2D', 'UpBlock2D')    ,   )
            return model







       def       snake_case (				self      :			int   ):







            """simple docstring"""







            __lowercase      		=self.dummy_uncond_unet
            __lowercase      		=PNDMScheduler()

            __lowercase      		=PNDMPipeline(unet=__lowercase    ,   scheduler=__lowercase   )
            pndm.to(__lowercase   )
            pndm.set_progress_bar_config(disable=__lowercase   )

            __lowercase      		=torch.manual_seed(0   )
            __lowercase      		=pndm(generator=__lowercase    ,   num_inference_steps=20    ,   output_type='numpy'   ).images

            __lowercase      		=torch.manual_seed(0   )
            __lowercase      		=pndm(generator=__lowercase    ,   num_inference_steps=20    ,   output_type='numpy'    ,   return_dict=__lowercase   )[0]

            __lowercase      		=image[0, -3:, -3:, -1]
            __lowercase      		=image_from_tuple[0, -3:, -3:, -1]

            assert image.shape == (1, 32, 32, 3)
            __lowercase      		=np.array([1.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 0.0, 0.0]   )

            assert np.abs(image_slice.flatten() - expected_slice   ).max() < 1E-2
            assert np.abs(image_from_tuple_slice.flatten() - expected_slice   ).max() < 1E-2






@slow
@require_torch
class 	lowerCAmelCase  (   unittest.TestCase ):







       def       snake_case (				self      :			Union[str, Any]   ):







            """simple docstring"""







            __lowercase      		='google/ddpm-cifar10-32'

            __lowercase      		=UNetaDModel.from_pretrained(__lowercase   )
            __lowercase      		=PNDMScheduler()

            __lowercase      		=PNDMPipeline(unet=__lowercase    ,   scheduler=__lowercase   )
            pndm.to(__lowercase   )
            pndm.set_progress_bar_config(disable=__lowercase   )
            __lowercase      		=torch.manual_seed(0   )
            __lowercase      		=pndm(generator=__lowercase    ,   output_type='numpy'   ).images

            __lowercase      		=image[0, -3:, -3:, -1]

            assert image.shape == (1, 32, 32, 3)
            __lowercase      		=np.array([0.1_5_6_4, 0.1_4_6_4_5, 0.1_4_0_6, 0.1_4_7_1_5, 0.1_2_4_2_5, 0.1_4_0_4_5, 0.1_3_1_1_5, 0.1_2_1_7_5, 0.1_2_5]   )

            assert np.abs(image_slice.flatten() - expected_slice   ).max() < 1E-2


