UOJ Logo Universal Online Judge

UOJ

#256. 【Rujia Liu's Present 7】Stone Age

附件下载 统计

借助月光宝盒,HURRICANE小组的成员们来到了石器时代。在热闹的广场上,不同部落的原始人来来往往进进出出。

但是,石器时代是非常容易爆发冲突的。冲突爆发时,处于绝对优势地位的部落总是能够获胜。某一时刻一个部落在广场上有“绝对优势”,指的是该时刻在广场上此部落的人数比其他部落的人数之和还要多。

出于安全考虑,HURRICANE小组的成员都非常迫切的希望知道目前在广场上哪个部落有绝对优势。但不幸的是,HURRICANE小组成员们只能判断两个原始人是不是属于一个部落。你的任务就是协助HURRICANE小组!

任务

你需要处理三种事件:

  1. 询问当前是否有绝对优势部落。
  2. 广场上新来一个人。
  3. 广场上一个人离开了。

你只能询问两个人是否同属一个部落,并且每个事件中,次数都被限制。

交互格式

你可以通过输出一行 Getjob 来开始一个新事件。

交互库会给出一个整数 $v$ 表示事件类型,具体地:

  • 若 $v=-2$,评测结束。
  • 若 $v=-1$,表示一次询问。
  • 若 $v=0$,表示新来了一个人,编号为上一个来的人标号 $+1$,第一个人编号为 $1$。
  • 若 $v\gt 0$,表示编号为 $v$ 的人离开了。

你可以输出如下操作来和交互库交互:

  1. Query i j 询问 $i$ 和 $j$ 是否同属一个部落。
    • 若同属一个部落,交互库返回 $1$,否则返回 $0$,注意,在每次询问事件中,你不能 Query
  2. Answer i 返回当前的绝对优势部落,$i=0$ 表示不存在绝对优势部落,否则表示 $i$ 所在部落为绝对优势部落,注意,$i$ 必须为 $0$ 或为一个在广场上的人。
    • 交互库不会返回任何信息。注意,在每次询问事件中,你必须进行恰好一次 Answer

每个事件中,你至多进行 $5$ 次 Query

样例

交互库输出 选手程序输出
$~$ Getjob
0 $~$
$~$ Getjob
0 $~$
$~$ Query 1 2
0 $~$
$~$ Getjob
-1 $~$
$~$ Answer 0
$~$ Getjob
0 $~$
$~$ Query 2 3
1 $~$
$~$ Getjob
-1 $~$
$~$ Answer 2
$~$ Getjob
2 $~$
$~$ Getjob
-1 $~$
$~$ Answer 0
$~$ Getjob
1 $~$
$~$ Getjob
-2 $~$

explanation

他们所在部落分别为 $1,2,2$。

数据范围与提示

保证事件数不超过 $100000$ 个。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

来源

Uva Online Judge,CTSC2004,题目作者刘汝佳。

特别鸣谢:各位验题人