175872025-08-05 09:24:57peti1234Passportscpp17Wrong answer 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
*/
SubtaskSumTestVerdictTimeMemory
00/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
3Accepted1ms316 KiB
4Accepted1ms500 KiB
15/5
5Accepted1ms316 KiB
6Accepted1ms412 KiB
7Accepted1ms316 KiB
8Accepted1ms316 KiB
9Accepted1ms316 KiB
28/8
10Accepted1ms316 KiB
11Accepted1ms320 KiB
12Accepted1ms500 KiB
13Accepted1ms564 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Accepted1ms500 KiB
17Accepted1ms316 KiB
18Accepted1ms564 KiB
19Accepted1ms316 KiB
20Accepted1ms316 KiB
21Accepted1ms500 KiB
30/7
22Accepted1ms500 KiB
23Accepted1ms564 KiB
24Accepted1ms408 KiB
25Accepted1ms316 KiB
26Accepted1ms508 KiB
27Accepted1ms316 KiB
28Accepted1ms564 KiB
29Accepted1ms508 KiB
30Wrong answer1ms316 KiB
31Accepted1ms412 KiB
32Accepted1ms316 KiB
33Accepted1ms444 KiB
412/12
34Accepted2ms564 KiB
35Accepted4ms832 KiB
36Accepted1ms316 KiB
37Accepted2ms316 KiB
38Accepted3ms316 KiB
39Accepted4ms316 KiB
40Accepted7ms548 KiB
41Accepted13ms564 KiB
42Accepted27ms928 KiB
43Accepted1ms316 KiB
44Accepted2ms380 KiB
45Accepted2ms332 KiB
46Accepted4ms472 KiB
47Accepted7ms316 KiB
48Accepted14ms564 KiB
49Accepted27ms924 KiB
50/13
50Wrong answer21ms820 KiB
51Accepted8ms1016 KiB
52Accepted2ms316 KiB
53Wrong answer2ms316 KiB
54Accepted2ms356 KiB
55Skipped0s0 KiB
56Skipped0s0 KiB
57Skipped0s0 KiB
58Skipped0s0 KiB
59Skipped0s0 KiB
615/15
60Accepted112ms2356 KiB
61Accepted35ms2356 KiB
62Accepted108ms2356 KiB
63Accepted105ms2356 KiB
64Accepted109ms2356 KiB
65Accepted115ms2356 KiB
66Accepted109ms2356 KiB
67Accepted116ms2356 KiB
68Accepted108ms2356 KiB
69Accepted1ms316 KiB
70Accepted1ms564 KiB
71Accepted1ms316 KiB
72Accepted2ms500 KiB
73Accepted2ms316 KiB
74Accepted2ms316 KiB
75Accepted2ms316 KiB
76Accepted2ms316 KiB
77Accepted3ms316 KiB
78Accepted4ms508 KiB
79Accepted4ms316 KiB
80Accepted4ms484 KiB
81Accepted7ms396 KiB
82Accepted7ms508 KiB
83Accepted7ms316 KiB
84Accepted14ms672 KiB
85Accepted13ms640 KiB
86Accepted14ms672 KiB
87Accepted28ms900 KiB
88Accepted28ms820 KiB
89Accepted27ms820 KiB
90Accepted56ms1320 KiB
91Accepted59ms1296 KiB
92Accepted52ms1332 KiB
93Accepted114ms2228 KiB
94Accepted111ms2272 KiB
95Accepted111ms2356 KiB
96Accepted112ms2356 KiB
70/15
97Accepted111ms2356 KiB
98Wrong answer68ms2356 KiB
99Accepted32ms2548 KiB
100Accepted46ms2548 KiB
101Wrong answer57ms2224 KiB
102Accepted1ms568 KiB
103Skipped0s0 KiB
104Skipped0s0 KiB
105Skipped0s0 KiB
106Skipped0s0 KiB
107Skipped0s0 KiB
108Skipped0s0 KiB
109Skipped0s0 KiB
110Skipped0s0 KiB
111Skipped0s0 KiB
112Skipped0s0 KiB
113Skipped0s0 KiB
114Skipped0s0 KiB
115Skipped0s0 KiB
116Skipped0s0 KiB
117Skipped0s0 KiB
118Skipped0s0 KiB
119Skipped0s0 KiB
80/15
120Accepted490ms8500 KiB
121Accepted167ms8672 KiB
122Accepted122ms8492 KiB
123Accepted194ms8508 KiB
124Wrong answer257ms8500 KiB
125Accepted449ms8500 KiB
126Wrong answer165ms4368 KiB
127Skipped0s0 KiB
128Skipped0s0 KiB
129Skipped0s0 KiB
130Skipped0s0 KiB
131Skipped0s0 KiB
132Skipped0s0 KiB
133Skipped0s0 KiB
134Skipped0s0 KiB
135Skipped0s0 KiB
136Skipped0s0 KiB
137Skipped0s0 KiB
138Skipped0s0 KiB
90/10
139Time limit exceeded2.059s33076 KiB
140Accepted510ms33076 KiB
141Accepted546ms33076 KiB
142Accepted754ms33084 KiB
143Wrong answer1.077s33212 KiB
144Accepted1.912s33068 KiB
145Wrong answer990ms16692 KiB
146Skipped0s0 KiB
147Skipped0s0 KiB
148Skipped0s0 KiB
149Skipped0s0 KiB
150Skipped0s0 KiB
151Skipped0s0 KiB
152Skipped0s0 KiB
153Skipped0s0 KiB
154Skipped0s0 KiB
155Skipped0s0 KiB
156Skipped0s0 KiB
157Skipped0s0 KiB