docker_space/frontier_cs_8/local_checker.cpp

// Local checker: reads k, then a program, outputs step count mod P and instruction count
// Mirrors the logic from chk.cc exactly
#include <bits/stdc++.h>
using namespace std;

constexpr int P = 998244353;

struct MInt {
    int x;
    MInt(): x(0) {}
    MInt(long long v): x(int((v % P + P) % P)) {}
    MInt operator+(const MInt& b) const { int r = x + b.x; return MInt(r >= P ? r - P : r); }
    MInt operator-(const MInt& b) const { int r = x - b.x; return MInt(r < 0 ? r + P : r); }
    MInt operator*(const MInt& b) const { return MInt(1LL * x * b.x % P); }
    bool operator==(const MInt& b) const { return x == b.x; }
    bool operator!=(const MInt& b) const { return x != b.x; }
};

int main(int argc, char* argv[]) {
    long long k;
    cin >> k;
    MInt target(k);

    int n;
    cin >> n;
    if (n < 1 || n > 512) {
        cerr << "Invalid n=" << n << endl;
        return 1;
    }

    // a[i]: POP has 4 entries [pop_char, goto_idx, push_char, goto_idx]
    //        HALT has 2 entries [push_char, goto_idx]
    vector<vector<int>> a(n);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s == "POP") {
            a[i].resize(4);
            cin >> a[i][0]; // pop char
            string tmp;
            cin >> tmp; // GOTO
            cin >> a[i][1]; // goto target
            a[i][1]--;
            cin >> tmp; // PUSH
            cin >> a[i][2]; // push char
            cin >> tmp; // GOTO
            cin >> a[i][3]; // goto target
            a[i][3]--;
            if (a[i][0] < 1 || a[i][0] > 1024 || a[i][2] < 1 || a[i][2] > 1024) {
                cerr << "Char out of range at instruction " << i+1 << endl;
                return 1;
            }
            if (a[i][1] < 0 || a[i][1] >= n || a[i][3] < 0 || a[i][3] >= n) {
                cerr << "Goto out of range at instruction " << i+1 << endl;
                return 1;
            }
        } else if (s == "HALT") {
            a[i].resize(2);
            string tmp;
            cin >> tmp; // PUSH
            cin >> a[i][0]; // push char
            cin >> tmp; // GOTO
            cin >> a[i][1]; // goto target
            a[i][1]--;
            if (a[i][0] < 1 || a[i][0] > 1024) {
                cerr << "Char out of range at instruction " << i+1 << endl;
                return 1;
            }
            if (a[i][1] < 0 || a[i][1] >= n) {
                cerr << "Goto out of range at instruction " << i+1 << endl;
                return 1;
            }
        } else {
            cerr << "Unknown instruction type: " << s << " at line " << i+1 << endl;
            return 1;
        }
    }

    // dp[i][x] = (next_instr, step_count) when executing instruction i with top-of-stack x (0=empty)
    vector<array<optional<pair<int, MInt>>, 1025>> dp(n);
    vector<array<bool, 1025>> vis(n, array<bool, 1025>{});

    bool infinite = false;

    function<pair<int, MInt>(int, int)> solve = [&](int i, int x) -> pair<int, MInt> {
        if (dp[i][x]) return dp[i][x].value();
        if (vis[i][x]) {
            infinite = true;
            return {-1, MInt(0)};
        }
        vis[i][x] = true;

        if (a[i].size() == 4) {
            // POP instruction
            if (x == a[i][0]) {
                dp[i][x] = {a[i][1], MInt(1)};
            } else {
                auto [j, u] = solve(a[i][3], a[i][2]);
                if (infinite) return {-1, MInt(0)};
                auto [kk, v] = solve(j, x);
                if (infinite) return {-1, MInt(0)};
                dp[i][x] = {kk, u + v + MInt(1)};
            }
        } else {
            // HALT instruction
            if (x == 0) {
                dp[i][x] = {-1, MInt(1)};
            } else {
                auto [j, u] = solve(a[i][1], a[i][0]);
                if (infinite) return {-1, MInt(0)};
                auto [kk, v] = solve(j, x);
                if (infinite) return {-1, MInt(0)};
                dp[i][x] = {kk, u + v + MInt(1)};
            }
        }
        return dp[i][x].value();
    };

    auto [final_instr, steps] = solve(0, 0);

    if (infinite) {
        cout << "INFINITE (never halts)" << endl;
        return 1;
    }

    cout << "n=" << n << " steps_mod_P=" << steps.x << " target_mod_P=" << target.x;
    if (steps == target) {
        cout << " CORRECT";
        double ratio = 1.0 * (512 - n) / 512;
        cout << " score=" << ratio;
    } else {
        cout << " WRONG";
    }
    cout << endl;

    return 0;
}