Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
统计

题目描述

两个代码军队在对战,有一方是被动方,一方是主动方。战场可以描述为一个 $m$ 个位置的序列,序列每个位置的状态为被摧毁(1)或未被摧毁(0)。两方轮流操作:

被动方为先手,他有一个可重集 $A$,每次从 $A$ 中选择一个数长度 $L$,并把这个数删掉。然后选择一个没有被摧毁的长度为 $L$ 的区间。区间没有被摧毁当且仅当每个位置都是未被摧毁的。如果先手无法选出这么一个区间,就输了。如果先手把可重集删空了,先手就赢了。

主动方为后手,每次从先手选定的区间当中选择一个位置摧毁。

现在出题人向你宣战,你的代码需要打败交互库。给定 $m$ 和可重集 $A$,你可以选择作为被动方或者主动方。

交互

交互库会先运行你的代码中的

int solve(int m, std::vector<int> A)

其中 $m$,$A$ 的含义见题面,不保证 $A$ 已经排好序。你需要返回一个整数 0 或者 1,0 表示你选择被动方,1 表示你选择主动方。

如果你的选择是被动方,则接下来交互库会运行若干次你的代码中的

std::pair<int, int> get_ans0(int prev)

其中 $prev$ 表示交互库对上一次你的选择做的决策,如果是第一次运行这个函数则 $prev=-1$。你需要返回一个 pair $(x,y)$ 作为你的决策,你需要满足 $x \le y$ 并且 $L=y-x+1$ 是一个合法的长度。

如果你的选择是主动方,则接下来交互库会运行若干次你的代码中的

int get_ans1(std::pair<int, int> prev)

其中 $prev=(x,y)$ 表示交互库的决策,你需要返回一个数 $t$ 满足 $x \le t \le y$ 表示你的决策。

如果被动方输了,交互库就会立即停止并且给出判分。

样例交互库

样例交互库的输入:第一行两个整数 $|A|$ 和 $m$ ,第二行 $|A|$ 个正整数表示 $A$ 。

然后样例交互库会输出一个数 0 或者 1 表示你的角色选择,0 表示被动方,1 表示主动方。

之后如果选手选择被动方,则之后若干次过程中交互库会先输出选手的决策,然后输入一个整数表示对手的决策。

如果选手选择主动方,则之后若干次过程中交互库会先输入两个整数表示对手的决策,然后输出一个整数表示选手的决策。

以上过程会执行直到被动方输或者赢,交互库会输出一行 passive win或者 passive lose并且退出程序。

数据范围

对于所有数据,满足 $|A| \le m \le 5000 $,$\forall x \in A$ 满足 $1 \le x \le m$。

down