不同顺子的牌组划分¶
预估时间限制：1.5 秒。内存限制：128 MB。
实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
牌具工坊收到几批带有种类和数字的牌。整理员想把全部牌装成规定的组合，其中相同的顺子只能装一次。
(本故事由GPT-6重写)
形式化问题描述¶
牌有 \(m\) 种，每种牌的数字可以是 \(1,\ldots,n\) .开始时没有牌，随后收到 \(k\) 批；第 \(i\) 批包含 \(a_i\) 张种类为 \(b_i\) 、数字为 \(c_i\) 的牌。同种同数字的牌只在数量上累加，不按批次区分。
判断能否把所有牌恰好使用一次，划分成以下两类组合：
- 顺子：同一种类、数字连续的三张或五张牌，每个数字恰好一张。任意两个顺子不能相同；即“种类、起始数字、长度”三者完全相同的顺子最多使用一个。
- 同牌组：种类和数字都相同的三张或四张牌。允许出现任意多个相同的同牌组。
两类组合都可以使用零组。不同种类或不同长度的顺子不视为相同。输出是否存在这样的划分。
输入格式¶
第一行三个整数 \(n,m,k\) .接下来 \(k\) 行，第 \(i\) 行三个整数 \(a_i,b_i,c_i\) .
输出格式¶
如果存在合法划分，输出一行 1 ；否则输出一行 0 .
样例¶
样例 1¶
输入¶
5 1 5
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
输出¶
1
样例 2¶
输入¶
3 1 3
2 1 1
2 1 2
2 1 3
输出¶
0
样例 3¶
输入¶
1 2 3
1 1 1
2 1 1
4 2 1
输出¶
1
样例解释¶
第一组使用一个长度为五的顺子。第二组若使用顺子，只能使用起点一、长度三的顺子一次，剩余三张牌无法组成合法组，因此无解。第三组把前两批的同牌累加成三张，再将另一种类的四张单独成组。
数据范围与保证¶
\(1\le n,m,k\le5\times10^6\) , \(1\le a_i\le10^9\) , \(1\le b_i\le m\) , \(1\le c_i\le n\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |