175882025-08-05 09:48:43peti1234Passportscpp17Accepted 100/1001.478s33256 KiB
#include <bits/stdc++.h>
using namespace std;

const int c=22, c2=(1<<c), inf=2e9;
int n, n2, si, k, kezd[c], veg[c], len[c], id[c], dp[c2], ki[c2], val[c], t[c], s[c], jo;
vector<int> sor;
void rec(int mask, int p) {
    if (mask==0) return;
    int ut=ki[mask];
    int el=mask-(1<<ut);
    s[id[ut]]=p, t[id[ut]]=dp[mask]-len[ut];
    rec(el, p);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	cin >> n >> k;
    n2=(1<<n);
    for (int i=0; i<n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        kezd[i]=a, veg[i]=a+b-1, len[i]=c, id[i]=i;
    }
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            if (kezd[j]<kezd[i]) {
                swap(kezd[i], kezd[j]);
                swap(veg[i], veg[j]);
                swap(len[i], len[j]);
                swap(id[i], id[j]);
            }
        }
    }
    for (int i=n-2; i>=0; i--) {
        if (veg[i]+1==kezd[i+1]) {
            veg[i]=veg[i+1];
        }
    }
    dp[0]=1;
    for (int i=1; i<n2; i++) {
        dp[i]=inf;
    }
    for (int mask=0; mask<n2; mask++) {
        int ert=dp[mask];
        int pos=0;
        for (int i=0; i<n; i++) {
            if (ert>=kezd[i]) {
                pos++;
            }
        }
        if (pos==n || ert==inf) continue;
        for (int i=0; i<n; i++) {
            if ((mask & (1<<i)) && veg[i]>ert) sor.push_back(i);
        }
        si=sor.size();
        for (int kov=0; kov<n; kov++) {
            if (mask & (1<<kov)) continue;
            if (ert+len[kov]>=kezd[kov]) continue;
 
            int lep=mask+(1<<kov);
            if ((pos==0 || ert>veg[pos-1]) && ((mask & (1<<pos))==0 || ert+len[kov]<kezd[pos]) && (si==0 || ert+len[kov]<kezd[sor[0]])) {
                if (ert+len[kov]<dp[lep]) {
                    dp[lep]=ert+len[kov];
                    ki[lep]=kov;
                }
                continue;
            }
 
            for (int i=0; i<sor.size(); i++) {
                int s=veg[sor[i]]+len[kov]+1;
                if (s>=kezd[kov]) break;
                if (i==si-1 || s<kezd[sor[i+1]]) {
                    if (s<dp[lep]) {
                        dp[lep]=s;
                        ki[lep]=kov;
                    }
                    break;
                }
            }
        }
        sor.clear();
    }
 
 
    if (k==1) {
        if (dp[n2-1]<inf) {
            rec(n2-1, 1);
            jo=1;
        }
    }
    if (k==2) {
        for (int mask=0; mask<n2; mask++) {
            if (!jo && dp[mask]<inf && dp[n2-1-mask]<inf) {
                rec(mask, 1), rec(n2-1-mask, 2);
                jo=1;
            }
        }
    }
 
    if (!jo) {
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for (int i=0; i<n; i++) {
        cout << s[i] << " " << t[i] << "\n";
    }
 
}
SubtaskSumTestVerdictTimeMemory
00/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
3Accepted1ms316 KiB
4Accepted1ms316 KiB
15/5
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
8Accepted1ms384 KiB
9Accepted1ms316 KiB
28/8
10Accepted1ms520 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Accepted1ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms316 KiB
19Accepted1ms316 KiB
20Accepted1ms316 KiB
21Accepted1ms444 KiB
37/7
22Accepted1ms316 KiB
23Accepted1ms428 KiB
24Accepted1ms316 KiB
25Accepted1ms316 KiB
26Accepted1ms316 KiB
27Accepted1ms316 KiB
28Accepted1ms316 KiB
29Accepted1ms508 KiB
30Accepted1ms328 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms316 KiB
412/12
34Accepted2ms564 KiB
35Accepted4ms820 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted2ms396 KiB
39Accepted3ms316 KiB
40Accepted4ms576 KiB
41Accepted8ms692 KiB
42Accepted17ms952 KiB
43Accepted1ms316 KiB
44Accepted1ms316 KiB
45Accepted2ms376 KiB
46Accepted3ms316 KiB
47Accepted4ms316 KiB
48Accepted8ms692 KiB
49Accepted17ms948 KiB
513/13
50Accepted16ms820 KiB
51Accepted6ms820 KiB
52Accepted1ms316 KiB
53Accepted1ms316 KiB
54Accepted1ms316 KiB
55Accepted3ms316 KiB
56Accepted4ms564 KiB
57Accepted7ms628 KiB
58Accepted10ms920 KiB
59Accepted9ms952 KiB
615/15
60Accepted71ms2380 KiB
61Accepted26ms2372 KiB
62Accepted78ms2412 KiB
63Accepted76ms2392 KiB
64Accepted78ms2356 KiB
65Accepted76ms2360 KiB
66Accepted71ms2412 KiB
67Accepted79ms2356 KiB
68Accepted75ms2356 KiB
69Accepted1ms316 KiB
70Accepted1ms316 KiB
71Accepted1ms316 KiB
72Accepted1ms316 KiB
73Accepted1ms316 KiB
74Accepted1ms316 KiB
75Accepted2ms316 KiB
76Accepted2ms468 KiB
77Accepted2ms316 KiB
78Accepted3ms508 KiB
79Accepted3ms476 KiB
80Accepted3ms500 KiB
81Accepted4ms564 KiB
82Accepted4ms316 KiB
83Accepted4ms564 KiB
84Accepted9ms564 KiB
85Accepted8ms564 KiB
86Accepted8ms568 KiB
87Accepted18ms820 KiB
88Accepted19ms904 KiB
89Accepted17ms820 KiB
90Accepted35ms1380 KiB
91Accepted39ms1384 KiB
92Accepted35ms1308 KiB
93Accepted79ms2420 KiB
94Accepted71ms2392 KiB
95Accepted71ms2488 KiB
96Accepted71ms2292 KiB
715/15
97Accepted72ms2476 KiB
98Accepted41ms2540 KiB
99Accepted21ms2356 KiB
100Accepted35ms2356 KiB
101Accepted37ms2356 KiB
102Accepted1ms316 KiB
103Accepted1ms316 KiB
104Accepted1ms316 KiB
105Accepted1ms316 KiB
106Accepted2ms316 KiB
107Accepted2ms316 KiB
108Accepted3ms704 KiB
109Accepted3ms316 KiB
110Accepted4ms568 KiB
111Accepted4ms756 KiB
112Accepted8ms676 KiB
113Accepted9ms700 KiB
114Accepted10ms952 KiB
115Accepted18ms924 KiB
116Accepted24ms1464 KiB
117Accepted35ms1332 KiB
118Accepted54ms2392 KiB
119Accepted61ms2356 KiB
815/15
120Accepted331ms8496 KiB
121Accepted104ms8504 KiB
122Accepted85ms8500 KiB
123Accepted143ms8504 KiB
124Accepted170ms8500 KiB
125Accepted312ms8632 KiB
126Accepted115ms4404 KiB
127Accepted243ms8500 KiB
128Accepted129ms4484 KiB
129Accepted259ms8500 KiB
130Accepted160ms4328 KiB
131Accepted231ms8628 KiB
132Accepted108ms4404 KiB
133Accepted298ms8500 KiB
134Accepted143ms4404 KiB
135Accepted214ms8500 KiB
136Accepted142ms4372 KiB
137Accepted303ms8500 KiB
138Accepted314ms8500 KiB
910/10
139Accepted1.393s33076 KiB
140Accepted291ms33076 KiB
141Accepted375ms33076 KiB
142Accepted512ms33076 KiB
143Accepted726ms33192 KiB
144Accepted1.335s33096 KiB
145Accepted703ms16692 KiB
146Accepted765ms33076 KiB
147Accepted425ms16696 KiB
148Accepted1.478s33112 KiB
149Accepted646ms16692 KiB
150Accepted1.187s33248 KiB
151Accepted517ms16692 KiB
152Accepted884ms33076 KiB
153Accepted554ms16692 KiB
154Accepted1.044s33076 KiB
155Accepted595ms17016 KiB
156Accepted1.217s33224 KiB
157Accepted1.37s33256 KiB