C. Leaving the Bar

Codeforces

IDCF995C

Time2000ms

Memory256MB

Difficulty—

brute forcedata structuresgeometrygreedymathsortings

English · Original

Chinese · Translation

Formal · Original

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}$. 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}$. Allen 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. ## Input The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of moves. Each 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$. ## Output Output 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$. It can be shown that a solution always exists under the given constraints. [samples]

对于向量 $\vec{v} = (x, y)$，定义 $| \vec{v} | = \sqrt{x^2 + y^2}$。艾伦在酒吧喝得太多，而酒吧位于原点。现有 $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}$。艾伦不希望离家（也就是酒吧）太远。你需要帮他找出一个移动序列（即每个向量的符号序列），使得他的最终位置 $p$ 满足 $| p | \leq 1.5 \times 10^6$，从而确保他的安全。第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——移动次数。接下来的每一行包含两个用空格分隔的整数 $x_i$ 和 $y_i$，表示 $\vec{v_i} = (x_i, y_i)$。我们有 $| \vec{v_i} | \leq 10^6$ 对所有 $i$ 成立。输出一行包含 $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$。可以证明，在给定约束下，解总是存在的。 ## Input 第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——移动次数。接下来的每一行包含两个用空格分隔的整数 $x_i$ 和 $y_i$，表示 $\vec{v_i} = (x_i, y_i)$。我们有 $| \vec{v_i} | \leq 10^6$ 对所有 $i$ 成立。 ## Output 输出一行包含 $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$。可以证明，在给定约束下，解总是存在的。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 10^5 $. Let $ \vec{v}_i = (x_i, y_i) \in \mathbb{R}^2 $ for $ i = 1, \dots, n $, with $ \|\vec{v}_i\| \leq 10^6 $. Let $ c_i \in \{ -1, 1 \} $ be a choice of sign for each vector. Define the final position: $$ \vec{p} = \sum_{i=1}^n c_i \vec{v}_i $$ **Constraints** 1. $ \|\vec{v}_i\| \leq 10^6 $ for all $ i \in \{1, \dots, n\} $ 2. $ \|\vec{p}\| \leq 1.5 \times 10^6 $ **Objective** Find a sequence $ (c_1, c_2, \dots, c_n) \in \{ -1, 1 \}^n $ such that $ \|\vec{p}\| \leq 1.5 \times 10^6 $.

Samples

Input #1

Output #1

1 1 -1

Input #2

1
-824590 246031

Output #2

Input #3

8
-67761 603277
640586 -396671
46147 -122580
569609 -2112
400 914208
131792 309779
-850150 -486293
5272 721899

Output #3

1 1 1 1 1 1 1 -1

API Response (JSON)

{
  "problem": {
    "name": "C. 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": "CF995C"
  },
  "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}$...",
      "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}$ ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 10^5 $.  \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 \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments