CSES - Shared codeLink to this code:
https://cses.fi/paste/00b85139a05218744e5888//*
* Keep it Simple!
* Do It Yourself!
*
* - Charles H. Moore, PROGRAMMING A PROBLEM-ORIENTED LANGUAGE (1970)
*/
#include <bits/stdc++.h>
namespace {
int64_t stack[2048];
int64_t *sp = stack;
int64_t retstack[2048];
int64_t *rp = retstack;
int64_t vars[2048];
}
template <size_t MaxLen = 10>
struct Str {
size_t size = 0;
char buf[1+MaxLen] = {};
constexpr Str() = default;
template <size_t N>
constexpr Str(const char (&s)[N]) {
std::copy(std::begin(s), std::end(s) - 1, buf);
size = std::end(s) - std::begin(s) - 1;
}
constexpr auto sv() const { return std::string_view(buf, buf+size); }
constexpr void push(char c) { buf[size++] = c; }
constexpr char operator[](size_t i) const { return buf[i]; }
constexpr auto operator<=>(const Str&) const = default;
};
template <size_t N>
Str(const char (&)[N]) -> Str<N - 1>;
struct WordList {
static const size_t Capacity = 512;
size_t size = 0;
Str<> buf[Capacity] = {};
constexpr WordList() = default;
template <Str<>... strs>
static constexpr WordList make() {
WordList wl;
(wl.push(strs), ...);
return wl;
}
template <size_t N>
static constexpr WordList split(const char (&s)[N]) {
return split(Str<N-1>(s));
}
template <size_t N>
static constexpr WordList split(const Str<N>& str) {
auto result = WordList();
Str<> acc;
for (size_t i = 0; i < str.size; i++) {
char c = str[i];
if (c == ' ' || c == '\n') {
if (acc.size > 0) {
result.push(acc);
acc = Str<>();
}
}
else {
acc.push(c);
}
}
if (acc.size > 0) {
result.push(acc);
}
return result;
}
constexpr void push(const Str<>& str) { buf[size++] = str; }
constexpr Str<> operator[](size_t i) const { return buf[i]; }
constexpr auto operator<=>(const WordList&) const = default;
constexpr size_t find_first(size_t begin, size_t end, const Str<>& x) const {
for (size_t it = begin; it != end; it++) {
if ((*this)[it] == x) {
return it;
}
}
return end;
}
constexpr size_t find_matching(size_t begin, size_t end, const Str<>& open, const Str<>& close) const {
size_t level = 0;
for (size_t it = begin; it != end; it++) {
level += (*this)[it] == open;
level -= (*this)[it] == close;
if (!level) return it;
}
return end;
}
constexpr size_t find_matching(size_t begin, size_t end, const Str<>& open, const Str<>& x, const Str<>& close) const {
size_t level = 0;
for (size_t it = begin; it != end; it++) {
level += (*this)[it] == open;
level -= (*this)[it] == close;
if (level == 1 && (*this)[it] == x) return it;
}
return end;
}
};
template <Str FS, typename T>
struct DictDef {
static constexpr auto name() { return FS; }
using Impl = T;
};
template <Str name, typename... Entries>
struct Lookup_impl;
template <Str name, typename Def, typename... Defs> requires (name == Def::name())
struct Lookup_impl<name, Def, Defs...> {
using type = typename Def::Impl;
};
template <Str name, typename Def, typename... Defs>
struct Lookup_impl<name, Def, Defs...> {
using type = typename Lookup_impl<name, Defs...>::type;
};
template <Str name, typename... Defs>
using Lookup = typename Lookup_impl<name, Defs...>::type;
template <size_t VarIndex> struct VariableEval { static void run() { *sp++ = reinterpret_cast<int64_t>(&vars[VarIndex]); } };
template <size_t VarIndex> struct ConstEval { static void run() { *sp++ = vars[VarIndex]; } };
template <size_t VC=0, typename... Defs>
struct Dictionary {
static constexpr size_t VarCount = VC;
template <Str name>
using lookup = Lookup<name, Defs...>;
template <Str name>
using add_var = Dictionary<VarCount+1, DictDef<name, VariableEval<VarCount>>, Defs...>;
template <Str name>
using add_const = Dictionary<VarCount+1, DictDef<name, ConstEval<VarCount>>, Defs...>;
template <Str name, typename Impl>
using add = Dictionary<VarCount, DictDef<name, Impl>, Defs...>;
template <template <Str> typename T, Str<>... names>
struct addT_impl;
template <template <Str> typename T>
struct addT_impl<T> {
using type = Dictionary<VC, Defs...>;
};
template <template <Str> typename T, Str<> name, Str<>... names>
struct addT_impl<T, name, names...> {
using type = typename add<name, T<name>>::template addT<T, names...>;
};
template <template <Str> typename T, Str<>... names>
using addT = typename addT_impl<T, names...>::type;
};
template <size_t N>
consteval std::optional<int64_t> to_number(const Str<N>& str) {
const size_t len = str.size;
const bool neg = len && str[0] == '-';
if (len - neg < 1) return {};
size_t base = 10;
size_t begin = neg;
if (len - begin >= 3 && str[begin] == '0' && str[begin+1] == 'x') {
begin += 2;
base = 16;
}
size_t x = 0;
for (size_t i = begin; i < len; i++) {
const char c = str[i];
int64_t digit = 0;
if (base == 16 && c >= 'A' && c <= 'F') {
digit = 10 + (c - 'A');
}
else if (c >= '0' && c <= '9') {
digit = c - '0';
}
else {
return {};
}
x = base*x + digit;
}
return neg ? -x : x;
}
template <typename DICT, Str word>
struct Word_eval {
using Impl = typename DICT::template lookup<word>;
static void run() { Impl::run(); }
};
template <typename DICT, Str word> requires (to_number(word).has_value())
struct Word_eval<DICT, word> {
static void run() { *sp++ = to_number(word).value(); }
};
template <Str<> name> struct Builtin { static bool run(); };
template <> struct Builtin<"."> { static void run() { std::cout << sp[-1] << ' '; sp--; } };
template <> struct Builtin<"+"> { static void run() { sp[-2] += sp[-1]; sp--; } };
template <> struct Builtin<"MOD"> { static void run() { sp[-2] %= sp[-1]; sp--; } };
template <> struct Builtin<"&"> { static void run() { sp[-2] &= sp[-1]; sp--; } };
template <> struct Builtin<"|"> { static void run() { sp[-2] |= sp[-1]; sp--; } };
template <> struct Builtin<"~"> { static void run() { sp[-1] = ~sp[-1]; } };
template <> struct Builtin<"-"> { static void run() { sp[-2] -= sp[-1]; sp--; } };
template <> struct Builtin<"/"> { static void run() { sp[-2] /= sp[-1]; sp--; } };
template <> struct Builtin<"*"> { static void run() { sp[-2] *= sp[-1]; sp--; } };
template <> struct Builtin<"="> { static void run() { sp[-2] = (sp[-2] == sp[-1]); sp--; } };
template <> struct Builtin<">"> { static void run() { sp[-2] = (sp[-2] > sp[-1]); sp--; } };
template <> struct Builtin<">="> { static void run() { sp[-2] = (sp[-2] >= sp[-1]); sp--; } };
template <> struct Builtin<"<"> { static void run() { sp[-2] = (sp[-2] < sp[-1]); sp--; } };
template <> struct Builtin<"OVER"> { static void run() { sp[0] = sp[-2]; sp++; } };
template <> struct Builtin<"DUP"> { static void run() { *sp = sp[-1]; sp++; } };
template <> struct Builtin<"ROT"> { static void run() { std::swap(sp[-1], sp[-2]); std::swap(sp[-1], sp[-3]); } };
template <> struct Builtin<"SWAP"> { static void run() { std::swap(sp[-1], sp[-2]); } };
template <> struct Builtin<"LSHIFT"> { static void run() { sp[-2] <<= sp[-1]; sp--; } };
template <> struct Builtin<"RSHIFT"> { static void run() { sp[-2] >>= sp[-1]; sp--; } };
template <> struct Builtin<"CR"> { static void run() { std::cout << '\n'; std::cout.flush(); } };
template <> struct Builtin<"DROP"> { static void run() { sp--; } };
template <> struct Builtin<">R"> { static void run() { *rp++ = *--sp; } };
template <> struct Builtin<"R>"> { static void run() { *sp++ = *--rp; } };
template <> struct Builtin<"I"> { static void run() { *sp++ = rp[-1]; } };
template <> struct Builtin<"I'"> { static void run() { *sp++ = rp[-2]; } };
template <> struct Builtin<"J"> { static void run() { *sp++ = rp[-3]; } };
template <> struct Builtin<"i64[]:new"> { static void run() { sp[-1] = (int64_t)new int64_t[sp[-1]]; } };
template <> struct Builtin<"@"> { static void run() { sp[-1] = *(int64_t*)sp[-1]; } };
template <> struct Builtin<"!"> { static void run() { *(int64_t*)sp[-1] = sp[-2]; sp -= 2; } };
template <> struct Builtin<"cin>>n"> { static void run() { std::cin >> *sp++; } };
template <> struct Builtin<"cin>>c"> { static void run() { char c; std::cin>>c; *sp++ = (int64_t)c; } };
template <> struct Builtin<"NOT"> { static void run() { sp[-1] = !sp[-1]; } };
template <> struct Builtin<"ABS"> { static void run() { sp[-1] = std::llabs(sp[-1]); } };
template <> struct Builtin<"MIN"> { static void run() { sp[-2] = std::min(sp[-2], sp[-1]); sp--; } };
template <> struct Builtin<"KTH-BIT"> { static void run() { sp[-2] = (sp[-2] >> sp[-1]) & 1; sp--; } };
template <> struct Builtin<"i64[]"> { static void run() { sp[-2] = ((int64_t*)sp[-2])[sp[-1]]; sp--; } };
template <Str<> str>
constexpr bool is_builtin = std::is_same_v<void, std::invoke_result_t<decltype(Builtin<str>::run)>>;
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
struct Forth_impl;
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
struct Forth_impl {
static void run() {
Word_eval<DICT, WL[IP]>::run();
Forth_impl<DICT, WL, IP+1, IPEnd>::run();
}
};
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
requires (IP >= IPEnd)
struct Forth_impl<DICT, WL, IP, IPEnd> {
static void run() { }
};
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
requires (IP+1 < IPEnd && WL[IP] == Str<>(":"))
struct Forth_impl<DICT, WL, IP, IPEnd> {
static constexpr size_t DefEnd = WL.find_matching(IP, IPEnd, ":", ";");
struct def {
static void run() {
Forth_impl<NEW_DICT, WL, IP+2, DefEnd>::run();
}
};
using NEW_DICT = typename DICT::template add<WL[IP+1], def>;
static void run() {
Forth_impl<NEW_DICT, WL, DefEnd+1, IPEnd>::run();
}
};
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
requires (IP < IPEnd && is_builtin<WL[IP]>)
struct Forth_impl<DICT, WL, IP, IPEnd> {
static void run() {
Builtin<WL[IP]>::run();
Forth_impl<DICT, WL, IP+1, IPEnd>::run();
}
};
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
requires (IP < IPEnd && WL[IP] == Str<>("?DO"))
struct Forth_impl<DICT, WL, IP, IPEnd> {
static constexpr size_t LoopEnd = WL.find_matching(IP, IPEnd, "?DO", "LOOP");
static void run() {
*rp++ = sp[-2];
*rp++ = sp[-1];
sp -= 2;
while (rp[-1] != rp[-2]) {
Forth_impl<DICT, WL, IP+1, LoopEnd>::run();
rp[-1]++;
}
rp -= 2;
Forth_impl<DICT, WL, LoopEnd+1, IPEnd>::run();
}
};
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
requires (IP < IPEnd && WL[IP] == Str<>("IF"))
struct Forth_impl<DICT, WL, IP, IPEnd> {
static constexpr size_t Then = WL.find_matching(IP, IPEnd, "IF", "THEN");
static constexpr size_t Else = WL.find_matching(IP, Then, "IF", "ELSE", "THEN");
static void run() {
int64_t top = sp[-1];
sp--;
if (top) {
Forth_impl<DICT, WL, IP+1, std::min(Then, Else)>::run();
}
else {
if constexpr (Else != IPEnd) {
Forth_impl<DICT, WL, Else + 1, Then>::run();
}
}
Forth_impl<DICT, WL, Then+1, IPEnd>::run();
}
};
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
requires (IP < IPEnd && WL[IP] == Str<>("BEGIN"))
struct Forth_impl<DICT, WL, IP, IPEnd> {
static constexpr size_t End = WL.find_matching(IP, IPEnd, "BEGIN", "UNTIL");
static void run() {
for (;;) {
Forth_impl<DICT, WL, IP+1, End>::run();
if (*--sp) break;
}
Forth_impl<DICT, WL, End+1, IPEnd>::run();
}
};
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
requires (IP+1 < IPEnd && WL[IP] == Str<>("VARIABLE"))
struct Forth_impl<DICT, WL, IP, IPEnd> {
static void run() {
using NEW_DICT = typename DICT::template add_var<WL[IP+1]>;
vars[DICT::VarCount] = 0;
Forth_impl<NEW_DICT, WL, IP+2, IPEnd>::run();
}
};
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
requires (IP+1 < IPEnd && WL[IP] == Str<>("CONSTANT"))
struct Forth_impl<DICT, WL, IP, IPEnd> {
static void run() {
using NEW_DICT = typename DICT::template add_const<WL[IP+1]>;
vars[DICT::VarCount] = *--sp;
Forth_impl<NEW_DICT, WL, IP+2, IPEnd>::run();
}
};
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
requires (IP < IPEnd && WL[IP] == Str<>("("))
struct Forth_impl<DICT, WL, IP, IPEnd> {
static constexpr size_t CommentEnd = WL.find_matching(IP, IPEnd, "(", ")");
static void run() {
Forth_impl<DICT, WL, CommentEnd+1, IPEnd>::run();
}
};
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
requires (IP < IPEnd && WL[IP] == Str<>(".\""))
struct Forth_impl<DICT, WL, IP, IPEnd> {
static constexpr size_t QuoteEnd = WL.find_first(IP, IPEnd, "\"");
static void run() {
for (size_t i = IP + 1; i < QuoteEnd; i++) {
std::cout << WL[i].sv() << ' ';
}
Forth_impl<DICT, WL, QuoteEnd+1, IPEnd>::run();
}
};
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
struct CompileDictionary {
using type = DICT;
};
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
requires (IP+1 < IPEnd && WL[IP] == Str<>(":"))
struct CompileDictionary<DICT, WL, IP, IPEnd> {
static constexpr size_t DefEnd = WL.find_matching(IP, IPEnd, ":", ";");
struct def { static void run() { Forth_impl<NEW_DICT, WL, IP+2, DefEnd>::run(); } };
using NEW_DICT = typename DICT::template add<WL[IP+1], def>;
using type = typename CompileDictionary<NEW_DICT, WL, DefEnd+1, IPEnd>::type;
};
template <typename DICT, WordList WL, size_t IP, size_t IPEnd>
requires (IP+1 < IPEnd && WL[IP] == Str<>("VARIABLE"))
struct CompileDictionary<DICT, WL, IP, IPEnd> {
using NEW_DICT = typename DICT::template add_var<WL[IP+1]>;
using type = typename CompileDictionary<NEW_DICT, WL, IP+2, IPEnd>::type;
};
template <Str str>
using Compile = typename CompileDictionary<Dictionary<>, WordList::split(str), 0, WordList::split(str).size>::type;
using Dict = Compile<R"cses(
: kth-digit ( n k -- d )
I 1 - SWAP -
: go ( n k -- d )
DUP IF
SWAP 10 / SWAP 1 - go
ELSE
DROP 10 MOD
THEN ;
go ;
: solve ( k -- ans )
1 -
VARIABLE $ans 1 $ans !
9 >R 1 >R
BEGIN
I I' *
OVER OVER >= IF
-
$ans @ I' + $ans !
R> R> 10 * >R 1 + >R
0
THEN
UNTIL
$ans @ OVER I / + $ans !
$ans @ SWAP I MOD kth-digit
R> DROP R> DROP ;
: main
cin>>n 0 ?DO
cin>>n solve . CR
LOOP ;
)cses">;
template <Str str>
using Forth = Forth_impl<Dict, WordList::split(str), 0, WordList::split(str).size>;
int main() {
std::cin.sync_with_stdio(0);
Forth<"main">::run();
}
