E. xortion

Codeforces

IDCF10088E

Time3000ms

Memory128MB

Difficulty—

English · Original

Formal · Original

Hussain doesn't like long statements’ problems, so he will describe his problem in a nutshell. Hussain will give you an array A[1….N] that consists of N positive integers. Hussain will ask you Q Queries each one consists of an integer number X . He wants you to find a number P : 1 ≤ P ≤ N such that (A[P]^X ≥ A[I]^X ) for each (1 ≤ I ≤ N). ^ Refers to “XOR” operation in computer science . In case of many possible values of P , take the minimum. The first line contains one number T – the number of testcases. The second line contains two space-separated numbers, N and Q (1 ≤ N ≤ 105, 1 ≤ Q ≤ 3×105) — the size of the array and the number of queries . The next line contains N space-separated integers the elements of the array A . All of them will fit into 32 bit signed integer. Next Q lines contain one integer X (also fits in 32 bit signed integer) which was described above. For each testcase output Q lines . The Ith line will contain the answer of the Ith query. Separate testcases by a blank line . Use fast I/O methods ## Input The first line contains one number T – the number of testcases. The second line contains two space-separated numbers, N and Q (1 ≤ N ≤ 105, 1 ≤ Q ≤ 3×105) — the size of the array and the number of queries . The next line contains N space-separated integers the elements of the array A . All of them will fit into 32 bit signed integer. Next Q lines contain one integer X (also fits in 32 bit signed integer) which was described above. ## Output For each testcase output Q lines . The Ith line will contain the answer of the Ith query. Separate testcases by a blank line . [samples] ## Note Use fast I/O methods

**Definitions** Let $ G = (V, E) $ be a directed acyclic graph (DAG), where $ V = \{1, 2, \dots, N\} $ is the set of nodes and $ E \subseteq V \times V $ is the set of directed edges ($ |E| = M $). Let $ s = 1 $ be Jorah’s starting node, and $ t = N $ be the target node (Khaleesi’s location). **Game Rules** - Players alternate turns, with Jorah moving first. - On Jorah’s turn: he moves along exactly one directed edge from his current node to an adjacent node. - On Khal’s turn: he removes exactly one existing edge from $ E $. - The game ends when: (i) Jorah reaches node $ N $ → Jorah wins; or (ii) Jorah is at a node with no outgoing edges → Khal wins. - Both players play optimally. **Constraints** 1. $ 1 \le T \le 10 $ 2. $ 2 \le N \le 100 $, $ 0 \le M \le 200 $ 3. No self-loops or multi-edges. 4. $ G $ is acyclic. **Objective** Determine the winner under optimal play: - If Jorah has a strategy to reach node $ N $ regardless of Khal’s edge removals, output "Jorah Mormont". - Otherwise, output "Khal Drogo".

API Response (JSON)

{
  "problem": {
    "name": "E. xortion",
    "description": {
      "content": "Hussain doesn't like long statements’ problems, so he will describe his problem in a nutshell.  Hussain will give you an array A[1….N] that consists of N positive integers.  Hussain will ask you Q Q",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 131072
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10088E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Hussain doesn't like long statements’ problems, so he will describe his problem in a nutshell. \n\nHussain will give you an array A[1….N] that consists of N positive integers. \n\nHussain will ask you Q Q...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be a directed acyclic graph (DAG), where $ V = \\{1, 2, \\dots, N\\} $ is the set of nodes and $ E \\subseteq V \\times V $ is the set of directed edges ($ |E| = M $). ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments