File size: 4,376 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 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 | #include <bits/stdc++.h>
using namespace std;
struct Label {
int pos = -1;
};
enum class InstrType { POP, HALT };
struct Instr {
InstrType type;
int a = 1, b = 1;
Label *x = nullptr, *y = nullptr;
};
struct Builder {
static constexpr int A_ALWAYS_MISMATCH = 1024;
static constexpr int TEMP_NOP = 1023;
static constexpr int TEMP_EXIT = 1022;
vector<Instr> prog;
vector<unique_ptr<Label>> labels;
int nextMarker = 1; // markers: 1..1021
Label* newLabel() {
labels.emplace_back(make_unique<Label>());
return labels.back().get();
}
void bind(Label* l) {
if (!l) return;
if (l->pos != -1) {
// Already bound; should not happen in this construction.
return;
}
l->pos = (int)prog.size() + 1;
}
void emitPopGoto(int a, Label* x, int b, Label* y) {
Instr in;
in.type = InstrType::POP;
in.a = a;
in.b = b;
in.x = x;
in.y = y;
prog.push_back(in);
}
void emitHalt(int b, Label* y) {
Instr in;
in.type = InstrType::HALT;
in.b = b;
in.y = y;
prog.push_back(in);
}
void emitPush(int v, Label* go) {
// Unconditional: a=1024 never appears on stack.
emitPopGoto(A_ALWAYS_MISMATCH, go, v, go);
}
void emitPopExpected(int v, Label* go) {
emitPopGoto(v, go, TEMP_NOP, go); // mismatch should never happen
}
void emitNOP(Label* cont) {
Label* afterPush = newLabel();
emitPush(TEMP_NOP, afterPush);
bind(afterPush);
emitPopExpected(TEMP_NOP, cont);
}
Label* buildEven(uint64_t E, Label* cont, Label* start = nullptr) {
if (E == 0) {
if (start != nullptr) {
// Not expected in this construction.
// Fall back: treat it as no-op by jumping to cont isn't possible without extra instruction.
}
return cont;
}
if (!start) start = newLabel();
bind(start);
if (E == 2) {
emitNOP(cont);
return start;
}
if (E == 4) {
Label* mid = newLabel();
emitNOP(mid);
buildEven(2, cont, mid);
return start;
}
if (E % 4 == 2) { // E >= 6
Label* rest = newLabel();
emitNOP(rest);
buildEven(E - 2, cont, rest);
return start;
}
// E % 4 == 0 and E >= 8
int marker = nextMarker++;
if (marker >= TEMP_EXIT) marker = 1; // should never happen
Label* bodyStart = newLabel();
Label* check = newLabel();
Label* popExit = newLabel();
emitPush(marker, bodyStart);
uint64_t L = E / 2 - 2;
buildEven(L, check, bodyStart);
bind(check);
// If top is marker, pop and repeat body; else push TEMP_EXIT and go popExit.
emitPopGoto(marker, bodyStart, TEMP_EXIT, popExit);
bind(popExit);
emitPopExpected(TEMP_EXIT, cont);
return start;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long k_in;
if (!(cin >> k_in)) return 0;
uint64_t k = (uint64_t)k_in;
uint64_t E = k - 1; // even
Builder b;
Label* halt = b.newLabel();
if (E > 0) {
Label* entry = b.newLabel();
b.buildEven(E, halt, entry);
}
// If E == 0, program starts at HALT.
b.bind(halt);
b.emitHalt(1, halt);
int n = (int)b.prog.size();
// Sanity: bind check
for (auto &lp : b.labels) {
if (lp->pos == -1) {
// Should not happen; bind to 1 to keep output valid.
lp->pos = 1;
}
}
if (n < 1) n = 1;
if (n > 512) {
// Should not happen with this construction; still output a trivial valid program.
cout << 1 << "\n";
cout << "HALT PUSH 1 GOTO 1\n";
return 0;
}
cout << n << "\n";
for (int i = 0; i < n; i++) {
const auto &in = b.prog[i];
if (in.type == InstrType::HALT) {
cout << "HALT PUSH " << in.b << " GOTO " << in.y->pos << "\n";
} else {
cout << "POP " << in.a << " GOTO " << in.x->pos
<< " PUSH " << in.b << " GOTO " << in.y->pos << "\n";
}
}
return 0;
} |