175882025-08-05 09:48:43peti1234Útlevelekcpp17Elfogadva 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";
    }
 
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
00/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
15/5
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
8Elfogadva1ms384 KiB
9Elfogadva1ms316 KiB
28/8
10Elfogadva1ms520 KiB
11Elfogadva1ms316 KiB
12Elfogadva1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms316 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva1ms316 KiB
19Elfogadva1ms316 KiB
20Elfogadva1ms316 KiB
21Elfogadva1ms444 KiB
37/7
22Elfogadva1ms316 KiB
23Elfogadva1ms428 KiB
24Elfogadva1ms316 KiB
25Elfogadva1ms316 KiB
26Elfogadva1ms316 KiB
27Elfogadva1ms316 KiB
28Elfogadva1ms316 KiB
29Elfogadva1ms508 KiB
30Elfogadva1ms328 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms316 KiB
412/12
34Elfogadva2ms564 KiB
35Elfogadva4ms820 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva2ms396 KiB
39Elfogadva3ms316 KiB
40Elfogadva4ms576 KiB
41Elfogadva8ms692 KiB
42Elfogadva17ms952 KiB
43Elfogadva1ms316 KiB
44Elfogadva1ms316 KiB
45Elfogadva2ms376 KiB
46Elfogadva3ms316 KiB
47Elfogadva4ms316 KiB
48Elfogadva8ms692 KiB
49Elfogadva17ms948 KiB
513/13
50Elfogadva16ms820 KiB
51Elfogadva6ms820 KiB
52Elfogadva1ms316 KiB
53Elfogadva1ms316 KiB
54Elfogadva1ms316 KiB
55Elfogadva3ms316 KiB
56Elfogadva4ms564 KiB
57Elfogadva7ms628 KiB
58Elfogadva10ms920 KiB
59Elfogadva9ms952 KiB
615/15
60Elfogadva71ms2380 KiB
61Elfogadva26ms2372 KiB
62Elfogadva78ms2412 KiB
63Elfogadva76ms2392 KiB
64Elfogadva78ms2356 KiB
65Elfogadva76ms2360 KiB
66Elfogadva71ms2412 KiB
67Elfogadva79ms2356 KiB
68Elfogadva75ms2356 KiB
69Elfogadva1ms316 KiB
70Elfogadva1ms316 KiB
71Elfogadva1ms316 KiB
72Elfogadva1ms316 KiB
73Elfogadva1ms316 KiB
74Elfogadva1ms316 KiB
75Elfogadva2ms316 KiB
76Elfogadva2ms468 KiB
77Elfogadva2ms316 KiB
78Elfogadva3ms508 KiB
79Elfogadva3ms476 KiB
80Elfogadva3ms500 KiB
81Elfogadva4ms564 KiB
82Elfogadva4ms316 KiB
83Elfogadva4ms564 KiB
84Elfogadva9ms564 KiB
85Elfogadva8ms564 KiB
86Elfogadva8ms568 KiB
87Elfogadva18ms820 KiB
88Elfogadva19ms904 KiB
89Elfogadva17ms820 KiB
90Elfogadva35ms1380 KiB
91Elfogadva39ms1384 KiB
92Elfogadva35ms1308 KiB
93Elfogadva79ms2420 KiB
94Elfogadva71ms2392 KiB
95Elfogadva71ms2488 KiB
96Elfogadva71ms2292 KiB
715/15
97Elfogadva72ms2476 KiB
98Elfogadva41ms2540 KiB
99Elfogadva21ms2356 KiB
100Elfogadva35ms2356 KiB
101Elfogadva37ms2356 KiB
102Elfogadva1ms316 KiB
103Elfogadva1ms316 KiB
104Elfogadva1ms316 KiB
105Elfogadva1ms316 KiB
106Elfogadva2ms316 KiB
107Elfogadva2ms316 KiB
108Elfogadva3ms704 KiB
109Elfogadva3ms316 KiB
110Elfogadva4ms568 KiB
111Elfogadva4ms756 KiB
112Elfogadva8ms676 KiB
113Elfogadva9ms700 KiB
114Elfogadva10ms952 KiB
115Elfogadva18ms924 KiB
116Elfogadva24ms1464 KiB
117Elfogadva35ms1332 KiB
118Elfogadva54ms2392 KiB
119Elfogadva61ms2356 KiB
815/15
120Elfogadva331ms8496 KiB
121Elfogadva104ms8504 KiB
122Elfogadva85ms8500 KiB
123Elfogadva143ms8504 KiB
124Elfogadva170ms8500 KiB
125Elfogadva312ms8632 KiB
126Elfogadva115ms4404 KiB
127Elfogadva243ms8500 KiB
128Elfogadva129ms4484 KiB
129Elfogadva259ms8500 KiB
130Elfogadva160ms4328 KiB
131Elfogadva231ms8628 KiB
132Elfogadva108ms4404 KiB
133Elfogadva298ms8500 KiB
134Elfogadva143ms4404 KiB
135Elfogadva214ms8500 KiB
136Elfogadva142ms4372 KiB
137Elfogadva303ms8500 KiB
138Elfogadva314ms8500 KiB
910/10
139Elfogadva1.393s33076 KiB
140Elfogadva291ms33076 KiB
141Elfogadva375ms33076 KiB
142Elfogadva512ms33076 KiB
143Elfogadva726ms33192 KiB
144Elfogadva1.335s33096 KiB
145Elfogadva703ms16692 KiB
146Elfogadva765ms33076 KiB
147Elfogadva425ms16696 KiB
148Elfogadva1.478s33112 KiB
149Elfogadva646ms16692 KiB
150Elfogadva1.187s33248 KiB
151Elfogadva517ms16692 KiB
152Elfogadva884ms33076 KiB
153Elfogadva554ms16692 KiB
154Elfogadva1.044s33076 KiB
155Elfogadva595ms17016 KiB
156Elfogadva1.217s33224 KiB
157Elfogadva1.37s33256 KiB