CFCF2180H2.Bug Is Feature (Conditional Version)

省选/NOI-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

这是该题的条件版本。这个版本与原问题的主要区别在于,“公差不减”这一条件的存在。只有你完成了所有版本的题目后,才能进行 Hack 操作。

请注意,这两个版本并不必然哪个更容易,并且它们可以独立地进行求解。

Bug 和 Feature 正沉浸在一种名为 Sequence 的游戏中。在这个独特版本的 Sequence 游戏中,游戏以三个正整数 a<b<cxa < b < c \le x 开始,并且三者构成一个等差数列(即 ba=cbb-a=c-b)。每当轮到玩家时,可以选择将 aabbcc 的其中一个增加一个正整数。操作后,三个数仍需保持等差数列(可能顺序会变化),且新的公差不能小于之前的公差。此外,aabbcc 均不能超过 xx

Bug 和 Feature 并不满足与常规的 Sequence 游戏,于是他们决定同时玩 nn 组 Sequence 游戏。对于第 ii 组游戏,给定五个数 ai<bi<ciliria_i < b_i < c_i \le l_i \le r_i。对于每一个 x[li,ri]x \in [l_i, r_i],他们要玩一个以 ai<bi<cixa_i < b_i < c_i \le x 为初始状态的游戏(一共要玩 i=1n(rili+1)\sum_{i=1}^n (r_i - l_i + 1) 个游戏)。两人交替进行所有这些游戏的回合,Bug 先手,然后 Feature。每回合,玩家选择任意一个未结束的游戏执行一次有效操作。无法进行操作的一方视为失败。

那么,若两人均以最优策略博弈,最终谁会获得胜利?

输入格式

每个测试用例包含多组数据。第一行包含整数 tt1t1051 \le t \le 10^5),表示测试用例的数量。

每个测试用例的第一行是一个整数 nn1n2×1051 \le n \le 2 \times 10^5),表示 Bug 和 Feature 要玩的游戏组数。

接下来的 nn 行,每行包含五个整数 ai,bi,ci,li,ria_i, b_i, c_i, l_i, r_i1ai<bi<ciliri10181 \le a_i < b_i < c_i \le l_i \le r_i \le 10^{18}),表示第 ii 组游戏的参数。aia_ibib_icic_i 形成等差数列(即 cibi=biaic_i-b_i=b_i-a_i)。

所有测试用例的 nn 之和不超过 2×1052 \times 10^5

输出格式

对于每组测试数据,输出一行,若 Bug 获胜则输出 Bug\mathtt{Bug},否则输出 Feature\mathtt{Feature}

输入输出样例

  • 输入#1

    5
    1
    1 3 5 5 6
    1
    2 4 6 8 10
    2
    4 6 8 10 11
    4 8 12 16 19
    1
    1 2 3 3 3
    1
    1000000000000 2000000000000 3000000000000 4000000000000 5000000000000

    输出#1

    Feature
    Bug
    Feature
    Feature
    Bug

说明/提示

在第一个样例中,游戏一开始就没有合法的操作。因此,Bug 无法进行任何操作,Feature 立即获胜。

在第二个样例中,有 33 个实例游戏,分别对应 x=8,9,10x=8,9,10。每个实例初始序列均为 2, 4, 62,\ 4,\ 6

Bug 可以这样取得胜利:

  1. 针对 x=10x=10 的实例,Bug 将 bb44 增加到 1010,此时序列变为 2,6,102,6,10。此时这个实例已经无法进行更多操作。
  2. 下一步 Feature 必须从剩余的两个实例中选择一个,将 aa22 增加到 88(无论是 x=8x=8 还是 x=9x=9 的游戏)。
  3. 无论 Feature 选择哪一个,Bug 都可以在另外一个实例中也将 aa 变为 88。此时这个实例也变为无法再操作的状态。

这样,所有的实例都进入了无法进行操作的状态,从而确保了 Bug 的胜利。

首页