File size: 2,802 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 | #include <bits/stdc++.h>
using namespace std;
constexpr long long P = 998244353;
constexpr int MAXSTATES = 31 * 31;
int d;
int g1_arr[30], gy_arr[30];
int ret_instr[MAXSTATES];
long long cost_arr[MAXSTATES];
int8_t status_arr[MAXSTATES];
struct Frame { int state; int8_t phase; int dep1, dep2; };
Frame stk[MAXSTATES * 2];
int stk_top;
inline int encode(int i, int x) { return i * (d + 1) + x; }
long long eval_fast() {
int ns = (d + 1) * (d + 1);
memset(status_arr, 0, ns);
stk_top = 0;
stk[stk_top++] = {encode(0, 0), 0, -1, -1};
while (stk_top > 0) {
Frame& f = stk[stk_top - 1];
int s = f.state, i = s / (d + 1), x = s % (d + 1);
if (f.phase == 0) {
if (status_arr[s] == 2) { stk_top--; continue; }
if (status_arr[s] == 1) return -1;
status_arr[s] = 1;
if (i < d) {
if (x == i + 1) { ret_instr[s] = g1_arr[i]; cost_arr[s] = 1; status_arr[s] = 2; stk_top--; continue; }
f.dep1 = encode(gy_arr[i], i + 1); f.phase = 1; stk[stk_top++] = {f.dep1, 0, -1, -1}; continue;
} else {
if (x == 0) { ret_instr[s] = -1; cost_arr[s] = 1; status_arr[s] = 2; stk_top--; continue; }
f.dep1 = encode(d, 1); f.phase = 1; stk[stk_top++] = {f.dep1, 0, -1, -1}; continue;
}
} else if (f.phase == 1) {
if (status_arr[f.dep1] != 2) return -1;
int j = ret_instr[f.dep1]; if (j < 0 || j > d) return -1;
f.dep2 = encode(j, x); f.phase = 2; stk[stk_top++] = {f.dep2, 0, -1, -1}; continue;
} else {
if (status_arr[f.dep2] != 2) return -1;
ret_instr[s] = ret_instr[f.dep2]; cost_arr[s] = (cost_arr[f.dep1] + cost_arr[f.dep2] + 1) % P;
status_arr[s] = 2; stk_top--;
}
}
return status_arr[encode(0, 0)] == 2 ? cost_arr[encode(0, 0)] : -1;
}
int main() {
d = 26;
mt19937 rng(42);
// Simple benchmark: random init + one mutation loop
for (int j = 0; j < d; j++) { g1_arr[j] = j + 1; gy_arr[j] = 0; }
auto t0 = chrono::steady_clock::now();
int count = 0;
long long T = eval_fast();
printf("Initial T = %lld\n", T);
for (int iter = 0; iter < 100000; iter++) {
int j = rng() % d;
int sv_g1 = g1_arr[j], sv_gy = gy_arr[j];
gy_arr[j] = rng() % (j + 1);
long long nT = eval_fast();
count++;
if (nT < 0) { gy_arr[j] = sv_gy; continue; }
if (nT != T) T = nT; // always accept for benchmarking
else gy_arr[j] = sv_gy;
}
auto t1 = chrono::steady_clock::now();
double ms = chrono::duration_cast<chrono::microseconds>(t1 - t0).count() / 1000.0;
printf("%d evals in %.1f ms (%.2f us/eval)\n", count, ms, ms*1000/count);
return 0;
}
|