175872025-08-05 09:24:57peti1234Útlevelekcpp17Hibás válasz 40/1002.059s33212 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=22, c2=(1<<c), inf=2e9;
int n, n2, k, kezd[c], veg[c], len[c], id[c], dp[c2], ki[c2], val[c], t[c], s[c], jo;
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() {
	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;
        vector<int> sor;
        for (int i=0; i<n; i++) {
            if ((mask & (1<<i)) && veg[i]>ert) sor.push_back(i);
        }
        int 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])) {
                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;
                }
            }
        }
    }


    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";
    }

}
/*
3 1
13 2 2
7 3 1
19 3 4
*/
RészfeladatÖsszpontTesztVerdiktIdőMemória
00/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
3Elfogadva1ms316 KiB
4Elfogadva1ms500 KiB
15/5
5Elfogadva1ms316 KiB
6Elfogadva1ms412 KiB
7Elfogadva1ms316 KiB
8Elfogadva1ms316 KiB
9Elfogadva1ms316 KiB
28/8
10Elfogadva1ms316 KiB
11Elfogadva1ms320 KiB
12Elfogadva1ms500 KiB
13Elfogadva1ms564 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms316 KiB
16Elfogadva1ms500 KiB
17Elfogadva1ms316 KiB
18Elfogadva1ms564 KiB
19Elfogadva1ms316 KiB
20Elfogadva1ms316 KiB
21Elfogadva1ms500 KiB
30/7
22Elfogadva1ms500 KiB
23Elfogadva1ms564 KiB
24Elfogadva1ms408 KiB
25Elfogadva1ms316 KiB
26Elfogadva1ms508 KiB
27Elfogadva1ms316 KiB
28Elfogadva1ms564 KiB
29Elfogadva1ms508 KiB
30Hibás válasz1ms316 KiB
31Elfogadva1ms412 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms444 KiB
412/12
34Elfogadva2ms564 KiB
35Elfogadva4ms832 KiB
36Elfogadva1ms316 KiB
37Elfogadva2ms316 KiB
38Elfogadva3ms316 KiB
39Elfogadva4ms316 KiB
40Elfogadva7ms548 KiB
41Elfogadva13ms564 KiB
42Elfogadva27ms928 KiB
43Elfogadva1ms316 KiB
44Elfogadva2ms380 KiB
45Elfogadva2ms332 KiB
46Elfogadva4ms472 KiB
47Elfogadva7ms316 KiB
48Elfogadva14ms564 KiB
49Elfogadva27ms924 KiB
50/13
50Hibás válasz21ms820 KiB
51Elfogadva8ms1016 KiB
52Elfogadva2ms316 KiB
53Hibás válasz2ms316 KiB
54Elfogadva2ms356 KiB
55Kihagyva0s0 KiB
56Kihagyva0s0 KiB
57Kihagyva0s0 KiB
58Kihagyva0s0 KiB
59Kihagyva0s0 KiB
615/15
60Elfogadva112ms2356 KiB
61Elfogadva35ms2356 KiB
62Elfogadva108ms2356 KiB
63Elfogadva105ms2356 KiB
64Elfogadva109ms2356 KiB
65Elfogadva115ms2356 KiB
66Elfogadva109ms2356 KiB
67Elfogadva116ms2356 KiB
68Elfogadva108ms2356 KiB
69Elfogadva1ms316 KiB
70Elfogadva1ms564 KiB
71Elfogadva1ms316 KiB
72Elfogadva2ms500 KiB
73Elfogadva2ms316 KiB
74Elfogadva2ms316 KiB
75Elfogadva2ms316 KiB
76Elfogadva2ms316 KiB
77Elfogadva3ms316 KiB
78Elfogadva4ms508 KiB
79Elfogadva4ms316 KiB
80Elfogadva4ms484 KiB
81Elfogadva7ms396 KiB
82Elfogadva7ms508 KiB
83Elfogadva7ms316 KiB
84Elfogadva14ms672 KiB
85Elfogadva13ms640 KiB
86Elfogadva14ms672 KiB
87Elfogadva28ms900 KiB
88Elfogadva28ms820 KiB
89Elfogadva27ms820 KiB
90Elfogadva56ms1320 KiB
91Elfogadva59ms1296 KiB
92Elfogadva52ms1332 KiB
93Elfogadva114ms2228 KiB
94Elfogadva111ms2272 KiB
95Elfogadva111ms2356 KiB
96Elfogadva112ms2356 KiB
70/15
97Elfogadva111ms2356 KiB
98Hibás válasz68ms2356 KiB
99Elfogadva32ms2548 KiB
100Elfogadva46ms2548 KiB
101Hibás válasz57ms2224 KiB
102Elfogadva1ms568 KiB
103Kihagyva0s0 KiB
104Kihagyva0s0 KiB
105Kihagyva0s0 KiB
106Kihagyva0s0 KiB
107Kihagyva0s0 KiB
108Kihagyva0s0 KiB
109Kihagyva0s0 KiB
110Kihagyva0s0 KiB
111Kihagyva0s0 KiB
112Kihagyva0s0 KiB
113Kihagyva0s0 KiB
114Kihagyva0s0 KiB
115Kihagyva0s0 KiB
116Kihagyva0s0 KiB
117Kihagyva0s0 KiB
118Kihagyva0s0 KiB
119Kihagyva0s0 KiB
80/15
120Elfogadva490ms8500 KiB
121Elfogadva167ms8672 KiB
122Elfogadva122ms8492 KiB
123Elfogadva194ms8508 KiB
124Hibás válasz257ms8500 KiB
125Elfogadva449ms8500 KiB
126Hibás válasz165ms4368 KiB
127Kihagyva0s0 KiB
128Kihagyva0s0 KiB
129Kihagyva0s0 KiB
130Kihagyva0s0 KiB
131Kihagyva0s0 KiB
132Kihagyva0s0 KiB
133Kihagyva0s0 KiB
134Kihagyva0s0 KiB
135Kihagyva0s0 KiB
136Kihagyva0s0 KiB
137Kihagyva0s0 KiB
138Kihagyva0s0 KiB
90/10
139Időlimit túllépés2.059s33076 KiB
140Elfogadva510ms33076 KiB
141Elfogadva546ms33076 KiB
142Elfogadva754ms33084 KiB
143Hibás válasz1.077s33212 KiB
144Elfogadva1.912s33068 KiB
145Hibás válasz990ms16692 KiB
146Kihagyva0s0 KiB
147Kihagyva0s0 KiB
148Kihagyva0s0 KiB
149Kihagyva0s0 KiB
150Kihagyva0s0 KiB
151Kihagyva0s0 KiB
152Kihagyva0s0 KiB
153Kihagyva0s0 KiB
154Kihagyva0s0 KiB
155Kihagyva0s0 KiB
156Kihagyva0s0 KiB
157Kihagyva0s0 KiB