{"problem":{"name":"B. Ithea Plays With Chtholly","description":{"content":"_This is an interactive problem. Refer to the Interaction section below for better understanding._ Ithea and Chtholly want to play a game in order to determine who can use the kitchen tonight. <cent","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF896B"},"statements":[{"statement_type":"Markdown","content":"_This is an interactive problem. Refer to the Interaction section below for better understanding._\n\nIthea and Chtholly want to play a game in order to determine who can use the kitchen tonight.\n\n<center>![image](https://espresso.codeforces.com/2dba15fc5c436b23cd2988708f9cd30993b18178.png)\n\n</center>Initially, Ithea puts _n_ clear sheets of paper in a line. They are numbered from 1 to _n_ from left to right.\n\nThis game will go on for _m_ rounds. In each round, Ithea will give Chtholly an integer between 1 and _c_, and Chtholly needs to choose one of the sheets to write down this number (if there is already a number before, she will erase the original one and replace it with the new one).\n\nChtholly wins if, at any time, all the sheets are filled with a number and the _n_ numbers are in non-decreasing order looking from left to right from sheet 1 to sheet _n_, and if after _m_ rounds she still doesn't win, she loses the game.\n\nChtholly really wants to win the game as she wants to cook something for Willem. But she doesn't know how to win the game. So Chtholly finds you, and your task is to write a program to receive numbers that Ithea gives Chtholly and help her make the decision on which sheet of paper write this number.\n\n## Input\n\nThe first line contains 3 integers _n_, _m_ and _c_ (, means rounded up) — the number of sheets, the number of rounds and the largest possible number Ithea can give to Chtholly respectively. The remaining parts of input are given throughout the interaction process.\n\n## Interaction\n\nIn each round, your program needs to read one line containing a single integer _p__i_ (1 ≤ _p__i_ ≤ _c_), indicating the number given to Chtholly.\n\nYour program should then output a line containing an integer between 1 and _n_, indicating the number of sheet to write down this number in.\n\n**After outputting each line, don't forget to flush the output.** For example:\n\n*   _fflush(stdout)_ in C/C++;\n*   _System.out.flush()_ in Java;\n*   _sys.stdout.flush()_ in Python;\n*   _flush(output)_ in Pascal;\n*   See the documentation for other languages.\n\n**If Chtholly wins at the end of a round, no more input will become available and your program should terminate normally.** It can be shown that under the constraints, it's always possible for Chtholly to win the game.\n\n[samples]\n\n## Note\n\nIn the example, Chtholly initially knew there were 2 sheets, 4 rounds and each number was between 1 and 4. She then received a 2 and decided to write it in the 1st sheet. Then she received a 1 and wrote it in the 2nd sheet. At last, she received a 3 and replaced 1 with 3 in the 2nd sheet. At this time all the sheets were filled with a number and they were non-decreasing, so she won the game.\n\n**Note that it is required that your program terminate immediately after Chtholly wins and do not read numbers from the input for the remaining rounds. If not, undefined behaviour may arise and it won't be sure whether your program will be accepted or rejected. Also because of this, please be careful when hacking others' codes.** In the sample, Chtholly won the game after the 3rd round, so it is required that your program doesn't read the number of the remaining 4th round.\n\nThe input format for hacking:\n\n*   The first line contains 3 integers _n_, _m_ and _c_;\n*   The following _m_ lines each contains an integer between 1 and _c_, indicating the number given to Chtholly in each round.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"_这是一个交互式问题。请参阅下面的交互部分以获得更好的理解。_\n\nIthea 和 Chtholly 想玩一个游戏，以决定今晚谁可以使用厨房。\n\n最初，Ithea 在一条直线上放置了 #cf_span[n] 张空白纸张。它们从左到右编号为 #cf_span[1] 到 #cf_span[n]。\n\n这个游戏将持续 #cf_span[m] 轮。在每一轮中，Ithea 会给出 Chtholly 一个介于 #cf_span[1] 和 #cf_span[c] 之间的整数，Chtholly 需要选择一张纸，将这个数字写在上面（如果之前已经有数字，她会擦掉原来的数字并用新数字替换）。\n\n如果在任何时候，所有纸张都被填满数字，并且从左到右（从第 #cf_span[1] 张纸到第 #cf_span[n] 张纸）的 #cf_span[n] 个数字呈非递减顺序，则 Chtholly 获胜；如果在 #cf_span[m] 轮结束后她仍未获胜，则她输掉游戏。\n\nChtholly 非常想赢得游戏，因为她想为 Willem 做些吃的。但她不知道如何获胜。于是 Chtholly 找到了你，你的任务是编写一个程序，接收 Ithea 给 Chtholly 的数字，并帮助她决定将这个数字写在哪张纸上。\n\n第一行包含 3 个整数 #cf_span[n, m] 和 #cf_span[c]（,  表示向上取整）— 分别为纸张数量、轮数以及 Ithea 可以给出的最大数字。输入的其余部分在交互过程中给出。\n\n在每一轮中，你的程序需要读取一行，其中包含一个整数 #cf_span[pi]（#cf_span[1 ≤ pi ≤ c]），表示 Ithea 给 Chtholly 的数字。\n\n然后，你的程序应输出一行，包含一个介于 #cf_span[1] 和 #cf_span[n] 之间的整数，表示将该数字写在第几张纸上。\n\n*每次输出后，请不要忘记刷新输出。* 例如：\n\n*如果 Chtholly 在某一轮结束时获胜，将不再有输入可用，你的程序应正常终止。* 可以证明，在给定约束下，Chtholly 总是可以获胜。\n\n在示例中，Chtholly 最初知道有 #cf_span[2] 张纸、#cf_span[4] 轮，每个数字介于 #cf_span[1] 和 #cf_span[4] 之间。她随后收到一个 #cf_span[2]，并决定将其写在第 #cf_span[1] 张纸上。然后她收到一个 #cf_span[1]，并将其写在第 #cf_span[2] 张纸上。最后，她收到一个 #cf_span[3]，并将第 #cf_span[2] 张纸上的 #cf_span[1] 替换为 #cf_span[3]。此时所有纸张都被填满，且数字呈非递减顺序，因此她赢得了游戏。\n\n*注意：必须在 Chtholly 获胜后立即终止程序，不再从输入中读取剩余轮次的数字。否则，可能会出现未定义行为，无法保证程序会被接受或拒绝。此外，正因为如此，请在 Hack 其他人的代码时格外小心。* 在示例中，Chtholly 在第 #cf_span[3] 轮后获胜，因此你的程序必须不再读取剩余的第 #cf_span[4] 轮的数字。\n\n用于 Hack 的输入格式：\n\n## Input\n\n第一行包含 3 个整数 #cf_span[n, m] 和 #cf_span[c]（,  表示向上取整）— 分别为纸张数量、轮数以及 Ithea 可以给出的最大数字。输入的其余部分在交互过程中给出。\n\n## Interaction\n\n在每一轮中，你的程序需要读取一行，其中包含一个整数 #cf_span[pi]（#cf_span[1 ≤ pi ≤ c]），表示 Ithea 给 Chtholly 的数字。你的程序应输出一行，包含一个介于 #cf_span[1] 和 #cf_span[n] 之间的整数，表示将该数字写在第几张纸上。*每次输出后，请不要忘记刷新输出。* 例如：   _fflush(stdout)_ 在 C/C++ 中；  _System.out.flush()_ 在 Java 中；  _sys.stdout.flush()_ 在 Python 中；  _flush(output)_ 在 Pascal 中；  请参阅其他语言的文档。 *如果 Chtholly 在某一轮结束时获胜，将不再有输入可用，你的程序应正常终止。* 可以证明，在给定约束下，Chtholly 总是可以获胜。\n\n[samples]\n\n## Note\n\n在示例中，Chtholly 最初知道有 #cf_span[2] 张纸、#cf_span[4] 轮，每个数字介于 #cf_span[1] 和 #cf_span[4] 之间。她随后收到一个 #cf_span[2]，并决定将其写在第 #cf_span[1] 张纸上。然后她收到一个 #cf_span[1]，并将其写在第 #cf_span[2] 张纸上。最后，她收到一个 #cf_span[3]，并将第 #cf_span[2] 张纸上的 #cf_span[1] 替换为 #cf_span[3]。此时所有纸张都被填满，且数字呈非递减顺序，因此她赢得了游戏。 *注意：必须在 Chtholly 获胜后立即终止程序，不再从输入中读取剩余轮次的数字。否则，可能会出现未定义行为，无法保证程序会被接受或拒绝。此外，正因为如此，请在 Hack 其他人的代码时格外小心。* 在示例中，Chtholly 在第 #cf_span[3] 轮后获胜，因此你的程序必须不再读取剩余的第 #cf_span[4] 轮的数字。用于 Hack 的输入格式：   第一行包含 3 个整数 #cf_span[n, m] 和 #cf_span[c]；  接下来的 #cf_span[m] 行每行包含一个介于 #cf_span[1] 和 #cf_span[c] 之间的整数，表示每轮 Ithea 给 Chtholly 的数字。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m, c \\in \\mathbb{Z}^+ $ denote the number of sheets, number of rounds, and maximum possible value, respectively.  \nLet $ P = (p_1, p_2, \\dots, p_m) $ be the sequence of integers provided by Ithea, where $ p_i \\in [1, c] $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the current state of the sheets, where $ a_j \\in [0, c] $ and $ a_j = 0 $ denotes an empty sheet.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 1000 $, $ 1 \\leq m \\leq 10000 $, $ 1 \\leq c \\leq 10^9 $  \n2. $ \\lceil \\frac{n}{2} \\rceil \\leq m $  \n3. $ p_i \\in [1, c] $ for all $ i \\in \\{1, \\dots, m\\} $  \n\n**Objective**  \nFor each round $ i \\in \\{1, \\dots, m\\} $:  \n- Read $ p_i $.  \n- Choose an index $ j \\in \\{1, \\dots, n\\} $ to assign $ a_j \\leftarrow p_i $.  \n- After the assignment, if $ a_j \\neq 0 $ for all $ j \\in \\{1, \\dots, n\\} $ and $ a_1 \\leq a_2 \\leq \\dots \\leq a_n $, terminate immediately.  \n\n**Strategy**  \nMaintain the array $ A $ such that it remains prefix-non-decreasing and suffix-non-increasing, with empty positions (0s) only in the middle.  \nFor each $ p_i $:  \n- If $ p_i \\leq \\min\\{a_j \\mid a_j > 0\\} $, place it at the leftmost empty or larger position to preserve non-decreasing order.  \n- If $ p_i \\geq \\max\\{a_j \\mid a_j > 0\\} $, place it at the rightmost empty or smaller position.  \n- Otherwise, place it in the leftmost position where $ a_j > p_i $, or rightmost where $ a_j < p_i $, ensuring the sequence remains sortable into non-decreasing order.  \n\n**Interaction**  \nFor each $ i \\in \\{1, \\dots, m\\} $:  \n1. Read $ p_i $.  \n2. Output $ j \\in \\{1, \\dots, n\\} $.  \n3. Update $ a_j \\leftarrow p_i $.  \n4. If all $ a_j > 0 $ and $ A $ is non-decreasing, terminate.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF896B","tags":["binary search","constructive algorithms","games","greedy","interactive"],"sample_group":[["2 4 4\n2\n1\n3","1\n2\n2"]],"created_at":"2026-03-03 11:00:39"}}