UOJ Logo Universal Online Judge

UOJ

#231. 【IOI2015】Teams

统计

班里有 $N$ 个学生,他们的编号是 $0$ 到 $N-1$。每天,老师都有一些项目需要学生去完成。每个项目都需要由一组学生在一天内完成。项目的难度可能不同。对于每个项目,老师知道该由多少学生组成的小组去完成。

不同的学生对小组的规模有不同的喜好。更准确的说,对学生 $i$ 而言,他只愿意待在人数在 $[A[i],B[i]]$ 内的小组工作。每一天,一个学生最多被分配到一个小组。有些学生可能不被分配到任何一个小组里。每个小组只负责一个项目。

老师已经选择好接下来 $Q$ 天每一天的项目。对于每一天,现需要判断是否有一种分配学生的方案,使得每个项目都有一个小组负责。

样例

现在有 $N=4$ 个学生,且有 $Q=2$ 天。每个学生对于小组规模的喜好如下:

学生 $0$:$A[0]=1, B[0]=2$

学生 $1$:$A[1]=2, B[1]=3$

学生 $2$:$A[2]=2, B[2]=3$

学生 $3$:$A[3]=2, B[3]=4$

第一天有 $M=2$ 个项目,需要的规模分别为 $K[0]=1$ 以及 $K[1]=1$。在这种情况下,没有一种适合学生的方案,因为只有学生 $0$ 愿意参加人数为 $1$ 的小组。

任务

给定对所有学生的描述:$N$, $A$ 以及 $B$ ,同时也给定 $Q$ 个问题的序列 —— 每天一个问题。每个问题包含当天要完成的 $M$ 个项目,同时含有一个长度为 $M$ 的序列 $K$,$K[i]$表示项目 $i$ 所需要的小组人数。对于每个问题,你的程序需要返回是否存在一种小组分配的方案,可以完成当天的所有项目。

你需要实现两个函数,他们分别是 $\mathrm{init}$ 和 $\mathrm{can}$:

  • $\mathrm{init}(N, A, B)$---- 测评库在开始时会调用该函数恰好一次。
    • $N$:学生的数目
    • $A$:一个长度为 $N$ 的数组,$A[i]$ 表示学生 $i$ 愿意加入的最少的小组人数
    • $B$:一个长度为 $N$ 的数组,$B[i]$ 表示学生 $i$ 愿意加入的最多的小组人数
    • 这个函数没有返回值
    • 你可以假设 $1 \le A[i] \le B[i] \le N$
  • $\mathrm{can}(M,K)$ ---当调用完一次 $init$ 后,测评库会连续调用该函数 $Q$ 次表示每一天的询问
    • $M$:当天要完成的项目数
    • $K$:一个长度为 $M$ 的数组,$K[i]$ 表示项目 $i$ 需要的小组规模
    • 如果存在一种分组完成当天的项目,返回 $1$,否则返回 $0$
    • 你可以假设 $1 \le M \le N, 1 \le K[i] \le N$。注意:$K[i]$ 之和可能大于 $N$

注意:不知道为什么,IOI 的官方数据存在 $M>N$ 的数据,但是保证 $M \le 200000$,请UOJ的用户在做的时候注意下

子任务

假设 $S$ 表示调用的 $\mathrm{can}(M,K)$ 的 $M$ 的总和。

子任务 得分 $N$ $Q$ 附加条件
121$1\leq N \leq 100$$1\leq Q\leq 100$没有
213$1\leq N \leq 100000$$Q=1$没有
343$1\leq N \leq 100000$$1\leq Q \leq 100000$$S\leq 100000$
423$1\leq N \leq 500000$$1\leq Q \leq 200000 $$S\leq 200000$

样例测评库

样例测评库将以下面的格式读入相关数据:

  • 第一行:$N$
  • 第 $2,\dots,N+1$ 行:$A[i]$ $B[i]$
  • 第 $N+2$ 行:$Q$
  • 第 $N+3, \dots, N+Q+2$ 行:$M$ $K[0]$ $K[1]$ $\dots$ $K[M-1]$

对于每个问题,样例测评库都会输出函数 $\mathrm{can}$ 的返回值

交互式类型的题目怎么本地测试

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

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

下载

样例及测评库下载