Add files using upload-large-folder tool

1fd0050 verified 6 months ago

4.47 kB

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

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