docker_space/frontier_cs_8/logs/gen_3.cpp

#include <bits/stdc++.h>
using namespace std;

static const long long P = 998244353;

// Use fixed-size array for speed
long long Sv[35];

inline long long computeT(int d, const int* gy) {
    Sv[0] = 0;
    for (int j = 0; j < d; j++) {
        long long c = ((Sv[j] - Sv[gy[j]] + (j - gy[j]) + 1) % P + P) % P;
        Sv[j + 1] = (Sv[j] + c) % P;
    }
    return (Sv[d] + d + 1) % P;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long k;
    cin >> k;

    if (k == 1) {
        cout << "1\nHALT PUSH 1 GOTO 1\n";
        return 0;
    }

    long long S = (k - 1) / 2;
    long long kmodP = k % P;

    // Strategy A: Exact single-modification block
    int exactD = -1, exactG = -1;
    for (int g = 0; g <= 31; g++) {
        long long val = S + (1LL << g);
        if (val > 0 && val <= (1LL << 31) && (val & (val - 1)) == 0) {
            int d = __builtin_ctzll(val);
            if (d > g && (exactD < 0 || d < exactD)) {
                exactD = d;
                exactG = g;
            }
        }
    }
    int bestN = (exactD > 0) ? exactD + 1 : 999;

    // Strategy B: Hill climbing mod P
    int hillD = -1;
    int hillGy[35];

    int maxTrialD = min(bestN - 2, 30);
    mt19937 rng((unsigned)(kmodP * 1000003ULL + 42));

    auto startTime = chrono::steady_clock::now();
    auto elapsed_ms = [&]() {
        return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - startTime).count();
    };

    int gy[35];

    // Determine minimum possible d:
    // For d where 2^(d+1) < P: computation is exact, max T = 2^(d+1)-1.
    // Skip d where kmodP > 2^(d+1)-1 (impossible).
    // For d where 2^(d+1) >= P: modular arithmetic applies, any target possible in theory.
    int minPossibleD = 1;
    for (int d = 1; d <= 30; d++) {
        long long maxT;
        if (d + 1 < 30) { // 2^(d+1) fits in long long and < P
            maxT = (1LL << (d + 1)) - 1;
            if (maxT < P && kmodP > maxT) {
                minPossibleD = d + 1;
                continue;
            }
        }
        break;
    }

    // Try d values from smallest possible
    for (int d = max(minPossibleD, 15); d <= maxTrialD; d++) {
        bool found = false;
        // Allocate time based on d
        int timeLimit;
        if (d <= minPossibleD + 2) timeLimit = 800; // Give the smallest possible d the most time
        else if (d <= minPossibleD + 4) timeLimit = 400;
        else timeLimit = 100;

        // Don't exceed total time budget
        if (elapsed_ms() > 1800) timeLimit = min(timeLimit, 50);

        int startMs = (int)elapsed_ms();
        for (int restart = 0; !found; restart++) {
            if ((int)elapsed_ms() - startMs > timeLimit) break;
            memset(gy, 0, sizeof(int) * d);
            for (int j = 1; j < d; j++) gy[j] = rng() % (j + 1);
            long long T = computeT(d, gy);

            int maxIter = 20000;
            for (int iter = 0; iter < maxIter; iter++) {
                if (T == kmodP) { found = true; break; }
                int j = 1 + rng() % (d - 1);
                int og = gy[j];
                int ng = rng() % (j + 1);
                if (ng == og) continue;
                gy[j] = ng;
                long long nT = computeT(d, gy);
                long long nd = min((nT - kmodP + P) % P, (kmodP - nT + P) % P);
                long long od = min((T - kmodP + P) % P, (kmodP - T + P) % P);
                if (nd <= od) { T = nT; }
                else { gy[j] = og; }
            }
            if (!found) {
                T = computeT(d, gy);
                if (T == kmodP) found = true;
            }
            if (found) {
                hillD = d;
                memcpy(hillGy, gy, sizeof(int) * d);
                break;
            }
        }
        if (found) break;
    }

    if (hillD > 0 && hillD + 1 < bestN) {
        bestN = hillD + 1;
        cout << bestN << "\n";
        for (int j = 0; j < hillD; j++) {
            cout << "POP " << (j+1) << " GOTO " << (j+2)
                 << " PUSH " << (j+1) << " GOTO " << (hillGy[j]+1) << "\n";
        }
        cout << "HALT PUSH 1 GOTO " << bestN << "\n";
        return 0;
    }

    if (exactD > 0) {
        cout << bestN << "\n";
        for (int j = 0; j < exactD; j++) {
            int g = (j == exactD - 1) ? exactG : 0;
            cout << "POP " << (j+1) << " GOTO " << (j+2)
                 << " PUSH " << (j+1) << " GOTO " << (g+1) << "\n";
        }
        cout << "HALT PUSH 1 GOTO " << bestN << "\n";
        return 0;
    }

    // Strategy C: Additive blocks fallback
    {
        int best_cost = 999;
        vector<int> best_dep;
        for (int m = 1; m <= 200; m++) {
            long long T = S + m;
            if (T & 1) continue;
            if (T < 2LL * m) continue;
            vector<int> bits;
            for (int b = 1; b <= 40; b++)
                if ((T >> b) & 1) bits.push_back(b);
            int pc = (int)bits.size();
            if (pc > m) continue;
            multiset<int> exps(bits.begin(), bits.end());
            int cost = 0;
            for (int b : bits) cost += b;
            bool valid = true;
            for (int s = 0; s < m - pc; s++) {
                auto it = exps.lower_bound(2);
                if (it == exps.end()) { valid = false; break; }
                int dd = *it; exps.erase(it);
                exps.insert(dd-1); exps.insert(dd-1);
                cost += (dd-2);
            }
            if (!valid) continue;
            int total = cost + 1;
            if (total < best_cost && total <= 512) {
                best_cost = total;
                best_dep.clear();
                for (int e : exps) best_dep.push_back(e);
            }
        }
        {
            long long remaining = S;
            int total_d = 0;
            vector<int> depths;
            while (remaining > 0) {
                int d = 1;
                while ((1LL << (d+1)) - 1 <= remaining) d++;
                depths.push_back(d);
                total_d += d;
                remaining -= (1LL << d) - 1;
            }
            int total = total_d + 1;
            if (total < best_cost && total <= 512) {
                best_cost = total;
                best_dep = depths;
            }
        }
        cout << best_cost << "\n";
        int pos = 1;
        for (int dd : best_dep) {
            int start = pos;
            for (int j = 1; j <= dd; j++) {
                cout << "POP " << j << " GOTO " << (start+j) << " PUSH " << j << " GOTO " << start << "\n";
                pos++;
            }
        }
        cout << "HALT PUSH 1 GOTO " << pos << "\n";
    }
    return 0;
}