{"problem":{"name":"E. Leaving the Bar","description":{"content":"For a vector $\\vec{v} = (x, y)$, define $|v| = \\sqrt{x^2 + y^2}$. Allen had a bit too much to drink at the bar, which is at the origin. There are $n$ vectors $\\vec{v_1}, \\vec{v_2}, \\cdots, \\vec{v_n}$","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF996E"},"statements":[{"statement_type":"Markdown","content":"For a vector $\\vec{v} = (x, y)$, define $|v| = \\sqrt{x^2 + y^2}$.\n\nAllen had a bit too much to drink at the bar, which is at the origin. There are $n$ vectors $\\vec{v_1}, \\vec{v_2}, \\cdots, \\vec{v_n}$. Allen will make $n$ moves. As Allen's sense of direction is impaired, during the $i$\\-th move he will either move in the direction $\\vec{v_i}$ or $-\\vec{v_i}$. In other words, if his position is currently $p = (x, y)$, he will either move to $p + \\vec{v_i}$ or $p - \\vec{v_i}$.\n\nAllen doesn't want to wander too far from home (which happens to also be the bar). You need to help him figure out a sequence of moves (a sequence of signs for the vectors) such that his final position $p$ satisfies $|p| \\le 1.5 \\cdot 10^6$ so that he can stay safe.\n\n## Input\n\nThe first line contains a single integer $n$ ($1 \\le n \\le 10^5$) — the number of moves.\n\nEach of the following lines contains two space-separated integers $x_i$ and $y_i$, meaning that $\\vec{v_i} = (x_i, y_i)$. We have that $|v_i| \\le 10^6$ for all $i$.\n\n## Output\n\nOutput a single line containing $n$ integers $c_1, c_2, \\cdots, c_n$, each of which is either $1$ or $-1$. Your solution is correct if the value of $p = \\sum_{i = 1}^n c_i \\vec{v_i}$, satisfies $|p| \\le 1.5 \\cdot 10^6$.\n\nIt can be shown that a solution always exists under the given constraints.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"对于向量 $\\vec{v} = (x, y)$，定义 $| \\vec{v} | = \\sqrt{x^2 + y^2}$。\n\n艾伦在酒吧喝得太多，而酒吧位于原点。现在有 $n$ 个向量 $\\vec{v_1}, \\vec{v_2}, \\dots, \\vec{v_n}$。艾伦将进行 $n$ 次移动。由于他的方向感受损，在第 $i$ 次移动中，他将沿着 $\\vec{v_i}$ 或 $-\\vec{v_i}$ 的方向移动。换句话说，如果他当前的位置是 $p = (x, y)$，他将移动到 $p + \\vec{v_i}$ 或 $p - \\vec{v_i}$。\n\n艾伦不希望离家（也就是酒吧）太远。你需要帮他找出一个移动序列（即每个向量的符号序列），使得他的最终位置 $p$ 满足 $| p | \\leq 1.5 \\times 10^6$，从而保证他的安全。\n\n第一行包含一个整数 $n$（$1 \\leq n \\leq 10^5$）——移动次数。\n\n接下来的每一行包含两个用空格分隔的整数 $x_i$ 和 $y_i$，表示 $\\vec{v_i} = (x_i, y_i)$。我们保证对所有 $i$ 都有 $| \\vec{v_i} | \\leq 10^6$。\n\n输出一行包含 $n$ 个整数 $c_1, c_2, \\dots, c_n$，每个整数为 $1$ 或 $-1$。你的解是正确的，当且仅当 $p = \\sum_{i=1}^n c_i \\vec{v_i}$ 满足 $| p | \\leq 1.5 \\times 10^6$。\n\n可以证明，在给定约束下，解总是存在的。\n\n## Input\n\n第一行包含一个整数 $n$（$1 \\leq n \\leq 10^5$）——移动次数。接下来的每一行包含两个用空格分隔的整数 $x_i$ 和 $y_i$，表示 $\\vec{v_i} = (x_i, y_i)$。我们保证对所有 $i$ 都有 $| \\vec{v_i} | \\leq 10^6$。\n\n## Output\n\n输出一行包含 $n$ 个整数 $c_1, c_2, \\dots, c_n$，每个整数为 $1$ 或 $-1$。你的解是正确的，当且仅当 $p = \\sum_{i=1}^n c_i \\vec{v_i}$ 满足 $| p | \\leq 1.5 \\times 10^6$。可以证明，在给定约束下，解总是存在的。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of vectors.  \nLet $ \\vec{v}_i = (x_i, y_i) \\in \\mathbb{R}^2 $ for $ i = 1, \\dots, n $, with $ \\|\\vec{v}_i\\| \\leq 10^6 $.  \nLet $ c_i \\in \\{-1, 1\\} $ be the sign chosen for vector $ \\vec{v}_i $.  \n\nDefine the final position:  \n$$\n\\vec{p} = \\sum_{i=1}^n c_i \\vec{v}_i\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ \\|\\vec{v}_i\\| \\leq 10^6 $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nFind a sequence $ (c_1, c_2, \\dots, c_n) \\in \\{-1, 1\\}^n $ such that:  \n$$\n\\|\\vec{p}\\| \\leq 1.5 \\times 10^6\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF996E","tags":["brute force","data structures","geometry","greedy","math","sortings"],"sample_group":[["3\n999999 0\n0 999999\n999999 0","1 1 -1"],["1\n-824590 246031","1"],["8\n-67761 603277\n640586 -396671\n46147 -122580\n569609 -2112\n400 914208\n131792 309779\n-850150 -486293\n5272 721899","1 1 1 1 1 1 1 -1"]],"created_at":"2026-03-03 11:00:39"}}