H. Perfect Ban

Codeforces

IDCF10134H

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Constantine and Mike are playing the board game «Wrath of Elves». There are n races and m classes of characters in this game. Each character is described by his race and class. For each race and each class there is exactly one character of this race and this class. The power of the character of the i-th race and the j-th class equals to aij, and both players know it perfectly. Now Constantine will choose a character for himself. Before that Mike can ban one race *and* one class so that Constantine would not be able to choose characters of this race *or* of this class. Of course, Mike does his best to leave Constantine the weakest possible character, while Constantine, on the contrary, chooses the strongest character. Which race and class Mike should ban? The first line contains two integers n and m (2 ≤ n, m ≤ 1000) separated by a space — the number of races and classes in the game «Wrath of Elves», correspondingly. The next n lines contain m integers each, separated by a space. The j-th number in the i-th of these lines is aij (1 ≤ aij ≤ 109). In the only line output two integers separated by a space — the number of race and the number of class Mike should ban. Races and classes are numbered from one. If there are several possible answers, output any of them. ## Input The first line contains two integers n and m (2 ≤ n, m ≤ 1000) separated by a space — the number of races and classes in the game «Wrath of Elves», correspondingly.The next n lines contain m integers each, separated by a space. The j-th number in the i-th of these lines is aij (1 ≤ aij ≤ 109). ## Output In the only line output two integers separated by a space — the number of race and the number of class Mike should ban. Races and classes are numbered from one. If there are several possible answers, output any of them. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the array. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers where $ 1 \leq a_i \leq 50 $. Let $ B = (b_1, b_2, \dots, b_n) $ be the output sequence, where each $ b_i $ is defined as follows. **Constraints** $ 1 \leq n \leq 10^5 $ **Objective** For each $ i \in \{1, \dots, n\} $, define: $$ b_i = \begin{cases} a_j & \text{if } j = \min\{ k \in \{i+1, \dots, n\} \mid a_k > a_i \} \\ -1 & \text{if no such } j \text{ exists} \end{cases} $$ Output $ B = (b_1, b_2, \dots, b_n) $.

API Response (JSON)

{
  "problem": {
    "name": "H. Perfect Ban",
    "description": {
      "content": "Constantine and Mike are playing the board game «Wrath of Elves». There are n races and m classes of characters in this game. Each character is described by his race and class. For each race and each ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10134H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Constantine and Mike are playing the board game «Wrath of Elves». There are n races and m classes of characters in this game. Each character is described by his race and class. For each race and each ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers where $ 1 \\leq a_i \\leq 50 $.  \nLet $ B = (b_1, b_2, \\dots, b_n)...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments