Submission #75822199

---

Source Code Expand

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;

int n, k;
vector<tuple<int, int, int, int, int>> v;
int ntom[100007];
bool vst[100007];
bool out[100007];
int mx;

void f(int node, int curr, int ret) {
    if (ret >= n) return;
    vst[node] = 1;
    v.emplace_back(node, ret, ret + (1 << curr) - 1, node * 2, node * 2 + 1);
    if (!curr) return;
    f(node * 2, curr - 1, ret);
    f(node * 2 + 1, curr - 1, ret + (1 << curr));
}

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);

    cin >> n >> k;
    if (n == k) {
        cout << 2 * n - 1 << '\n';
        for (int i = 1; i < n - 1; i++) {
            cout << i << ' ' << n + 1 << ' ' << i << '\n';
        }
        cout << n - 1 << ' ' << n - 1 << ' ' << n << '\n';
        cout << "0 0 0\n0 0 0\n";
        for (int i = n + 1; i < 2 * n - 1; i++) {
            cout << 2 * n - 2 - i << ' ' << (i + 1 == 2 * n - 1 ? 0 : (i + 1))
                 << ' ' << 2 * n - 1 - i << '\n';
        }
        exit(0);
    }
    int bits = ceil(log2(n));
    int time = bits + 1;
    if (k < time) cout << -1, exit(0);
    int gap = k - time;
    f(1, bits - 1, 0);
    sort(all(v));
    int start = 0;
    vector<tuple<int, int, int, int>> fk;
    if (gap) {
        fk.emplace_back(0, 0, 0, n + 1);
        for (int i = n + 1; i < n + gap; i++) {
            fk.emplace_back(i, 0, 0, i + 1);
        }
        start = n + gap;
    }
    int idx = start;
    int idx2 = 1;
    for (auto& [n1, ret, f, n2, n3] : v) {
        if (idx2 < ret)
            ntom[n1] = idx2++;
        else {
            ntom[n1] = idx;
            if (!idx)
                idx = n + 1;
            else
                idx++;
        }
    }
    for (int i = idx2; i <= n; i++) fk.emplace_back(i, 0, 0, 0);
    for (auto& [n1, ret, f, n2, n3] : v) {
        int bt = 1 << bits;
        int x2 = (n2 >= bt ? n2 - bt + 1 : ntom[n2]);
        int x3 = (n3 >= bt ? n3 - bt + 1 : ntom[n3]);
        fk.emplace_back(ntom[n1], f + 1, x2, x3);
    }
    sort(all(fk));
    if (fk.size() > 2048) cout << -1, exit(0);
    cout << fk.size() << '\n';
    for (auto& [i, f, n2, n3] : fk)
        cout << min(f, n) << ' ' << n2 << ' ' << n3 << '\n';
}

Submission Info

Judge Result