luogu#P5688. [CSP-S2019 江西] 散步
[CSP-S2019 江西] 散步
题目背景
JXCSP-S T4
题目描述
公园内有 个人正在散步,随着天色渐晚,所有人准备回家离开公园。公园的结构是一个首尾相连的环形图,它共有 个出口,为了方便叙述,我们将人从 编号,将出口按逆时针顺序从 编号。
公园总长 米,我们令 号出口所在的位置为 米,则 编号为 的出口在 号出口逆时针方向 米的位置上,其中 严格递增 ,即 号出口与 号出口相邻,由于公园是环形图,故 号出口与 号出口也相邻。每个出口还有一个通行限制 ,表示最多有 个人能从 号出口离开。
所有人回家时将按自己的朝向,可能是顺时针方向,也可能是逆时针方向不断前行,当他们走到一个还能离开的出口时,将从该出口离开公园。特别地,当两个人同时走到一个只能允许 个人离开的出口时,编号小的那个人能从该出口离开,编号较大的人将继续前进。
现在给定 个人所在的起始位置与他们的前进方向,请你求出每个人从哪个出口离开,若编号为 的 人从 号出口离开,你只需要给出 的异或和,即:
$$(1\times k_1) \operatorname{xor} (2\times k_2) \operatorname{xor}\cdots \operatorname{xor} (n\times k_n) $$其中 是位异或运算。特别地若一个人最后无法离开,则他的 。
输入格式
第一行三个正整数 ,意义见题目描述。
第二行 个正整数 表示出口位置。保证 严格递增。
第三行 个正整数 表示出口的人数限制。
接下来 行每行两个整数 。若 为 表示编号为 的人前进方向是逆时针方向,为 表示是顺时针方向。 表示编号为 的人的起始位置为:离 号出口逆时针方向 米的位置。
输出格式
仅一行一个整数表示答案。
3 2 5
2
2 1
0 1
1 3
0 4
3
3 2 5
2
1 1
0 0
0 2
0 1
5
提示
【输入输出样例 1 说明】
编号为 的人分别从 号出口离开。
【输入输出样例 2 说明】
编号为 的人分别从 号出口离开,编号为 的人无法离开公园。
【数据规模与约定】
对于 的数据:;
对于 的数据:,;
对于 的数据:;
另有 的数据:,所有 ;
对于 的数据:,,,,,。