File size: 4,471 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 | // 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;
}
|