Inestabilidad P64038


Statement
 

pdf   zip

thehtml

Se tiene un vector de pares distintos de enteros, y se desea ordenarlo en orden creciente según el primer entero de cada par. Por ejemplo, el vector:

(2, 5) (1, 8) (10, -3)

quedaría ordenado así:

(1, 8) (2, 5) (10, -3)

Para ordenar el vector usaremos un algoritmo de ordenación no estable, por lo tanto, puede haber más de una ordenación posible. Por ejemplo, el vector:

(2, 5) (-1, 0) (2, 8)

tiene dos ordenaciones posibles:

(-1, 0) (2, 5) (2, 8)

(-1, 0) (2, 8) (2, 5)

Haz un programa que, dado un vector de enteros, cuente cuántas ordenaciones correctas tiene.

Entrada

Para cada caso empieza con un entero n ≤ 100000, que es el tamaño del vector. A continuación hay n pares de enteros xi yi (1 ≤ in). No hay dos pares iguales, es decir: ∀ i, j 1 ≤ i, jn, ijxixjyiyj

Salida

Para cada caso, escribe el número de ordenaciones correctas del vector módulo 100000007.

Public test cases
  • Input

    2   1 2   2 3
    3   1 2   1 3   2 -99
    3   1 1   1 2   1 3
    4   1 2   1 3   2 2   2 3
    5   1 2   1 3   2 2   2 3   5 5
    

    Output

    1
    2
    6
    4
    4
    
  • Input

    2 1 2 2 3
    3 1 2 1 3 2 -99
    3 1 1 1 2 1 3
    4 1 2 1 3 2 2 2 3
    5 1 2 1 3 2 2 2 3 5 5
    

    Output

    1
    2
    6
    4
    4
    
  • Information
    Author
    Pol Mauri
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++