很神奇的 DP。
首先考虑到 \(P=2\) 实际上就是将一个集合划分成了两个不相交的集合，两个集合均合法则答案合法，那么我们可以考虑对每一个集合都求出答案。那么现在就只需要考虑 \(P=1\) 的情况了。发现 \(n \le 22\)，所以直接考虑状压。
为了合法并且给后面的签证留出时间，我们肯定想要让当前的签证尽可能快的办下来。那么我们设 \(f_S\) 为将 \(S\) 集合中的所有签证都申请下来的最短时间，DP 出这个数组后即可得到答案。
考虑如何 DP。此时集合为 \(S\)，考虑枚举一个 \(j\) 加入当前集合。
那么首先，假如在当前的时间，我们在某一个 \([l_i, r_i]\) 时间段内，那么我们肯定需要推迟到 \(r_i + 1\) 再考虑，因为这期间不可能申请任何签证。
其次，如果我们现在可以办一个签证，但在签证办好之前我们就需要出国，这时候这个签证也是不能办的。即如果有某个 \(f_{S \cup \{j\}} + t_j \ge l_i\)，那么 \(f_{S \cup \{j\}} \gets r_i + 1\)。
直接枚举所有 \(i\) 来 DP 就可以做到 \(O(n^2 2^n)\)，考虑优化。发现这个过程中只与 \(t_j\) 有关系，而 \(t_j\) 越大，\(f_{S \cup \{j\}}\) 一定会越大。那么我们可以按照 \(t_j\) 从小到大的顺序考虑，这样每次 \(j\) 改变，只需要从上一次的答案往下拓展即可。同理，对于 \(l_i\)，我们发现每次只会有更大的 \(l_i\) 会对答案造成贡献，所以我们仍然可以按照 \(l_i\) 从小到大维护一个指针，这样每次拓展时 \(i\) 可以从上一次的位置开始拓展。这样我们就做到了 \(O(n 2^n)\)。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 24;
const int inf = 0x3f3f3f3f;
struct Camp {
int l, r, len, t, id;
};
int n, P;
Camp c[MAXN], cl[MAXN], ct[MAXN];
int f[1 << MAXN], g[1 << MAXN];
int ans[MAXN][2];
void calc(int s, int i) {
if (f[s] == inf) return;
while (s) {
int x = g[s];
ans[x][0] = i;
ans[x][1] = f[s] - c[x].t;
s ^= (1 << (x - 1));
}
}
int main() {
scanf("%d%d", &n, &P);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &c[i].l, &c[i].len, &c[i].t);
c[i].r = c[i].l + c[i].len - 1, c[i].id = i;
ct[i] = cl[i] = c[i];
}
sort(cl + 1, cl + 1 + n, [&](auto &a, auto &b) { return a.l < b.l; });
sort(ct + 1, ct + 1 + n, [&](auto &a, auto &b) { return a.t < b.t; });
memset(f, 0x3f, sizeof f);
f[0] = 1;
for (int s = 0; s < (1 << n); s++) if (f[s] != inf) {
int t = f[s];
int s0 = 1, s1 = 1;
for (int j = 1; j <= n; j++) if (!(s >> (ct[j].id - 1) & 1)) {
while (true) {
while (s0 <= n && cl[s0].r < t) s0++;
while (s1 <= n && (cl[s1].l < t || !(s >> (cl[s1].id - 1) & 1))) s1++;
if (s0 <= n && cl[s0].l <= t) {
t = cl[s0].r + 1;
continue;
}
if (s1 <= n && cl[s1].l <= t + ct[j].t) {
t = cl[s1].r + 1;
continue;
}
break;
}
if (t + ct[j].t < ct[j].l) {
if (t + ct[j].t < f[s | (1 << (ct[j].id - 1))]) {
f[s | (1 << (ct[j].id - 1))] = t + ct[j].t;
g[s | (1 << (ct[j].id - 1))] = ct[j].id;
}
}
}
}
if (P == 1) calc((1 << n) - 1, 1);
else {
for (int s = 0; s < (1 << n); s++) {
if (f[s] != inf && f[((1 << n) - 1) ^ s] != inf) {
calc(s, 1);
calc(((1 << n) - 1) ^ s, 2);
break;
}
}
}
if (!ans[1][0]) printf("NO\n");
else {
printf("YES\n");
for (int i = 1; i <= n; i++) {
printf("%d %d\n", ans[i][0], ans[i][1]);
}
}
return 0;
}