Ohjelmat

#include <bits/stdc++.h>

using namespace std;

typedef uint64_t pino_key_t;
union pino_key_union_t {
    pino_key_t key;
    struct {
        pino_key_t pino_tulo_1 : 16, pino_tulo_2 : 16, pino_summa : 16, a : 8, b : 8;
    };
};

constexpr int PINOJA = 3;
unordered_map<pino_key_t, int> pinot[PINOJA];
unordered_map<int, pair<int, string>> ohjelmat;

int pino_[64] = {0, 0, 1};
int* const pino = &pino_[2];
int pino_summa = 1;
int pino_i = 0;
constexpr int pino_max = 8;
const char* komennot_[64] = {0};
const char** komennot = &komennot_[2];
constexpr int komennot_max = 20;
constexpr long tulos_max = 1000000;

const char *PLUS = "+ ", *MUL = "* ", *DUP = "DUP ", *DROP = "DROP ", *SWAP = "SWAP ", *OVER = "OVER ", *ROT = "ROT ";

void tulosta(int tulos, int pituus, string ohjelma) {
    ifstream f("3d.best." + to_string(tulos));
    int vanha_pituus;
    if (!(f >> vanha_pituus) || vanha_pituus > pituus) {
        ofstream f2("3d.best." + to_string(tulos));
        f2 << pituus << "\n" << ohjelma << "\n";
        cout << tulos << "\t" << pituus << "\t" << ohjelma << "\n";
    }
}

constexpr int primes_16[] = {65521, 65519, 65497, 65479, 65449, 65447, 65437, 65423, 65419, 65413, 65407, 65393, 65381, 65371, 65357, 65353};
constexpr int primes_8[] = {251, 241, 239, 233, 229, 227, 223, 211, 199, 197, 193, 191, 181, 179, 173, 167};

void dfs(int k) {
    if (k + pino_i > komennot_max) {
        return;
    }

    pino_key_union_t pino_key = {0};
    pino_key.pino_summa = pino_summa % primes_16[0];
    uint64_t pino_tulo_1 = 1, pino_tulo_2 = 1;
    for (int i = 0; i <= pino_i; i++) {
        pino_tulo_1 *= pino[i];
        pino_tulo_1 %= primes_16[1];
        pino_tulo_2 *= pino[i];
        pino_tulo_2 %= primes_16[2];
    }
    pino_key.pino_tulo_1 = pino_tulo_1;
    pino_key.pino_tulo_2 = pino_tulo_2;
    pino_key.a = pino[pino_i] % primes_8[0];
    pino_key.b = pino[pino_i-1] % primes_8[1];
    if (pinot[0].count(pino_key.key) && pinot[0][pino_key.key] <= k + pino_i) {
        return;
    }
    pinot[0][pino_key.key] = k + pino_i;
    if (pinot[0].size() > 20000000 / PINOJA) {
        swap(pinot[1], pinot[2]);
        swap(pinot[0], pinot[1]);
        pinot[0].clear();
    }
    for (int i = 1; i < PINOJA; i++) {
        if (pinot[i].count(pino_key.key) && pinot[i][pino_key.key] <= k + pino_i) {
            return;
        }
    }

    if (ohjelmat.count(pino_summa) && k + pino_i < ohjelmat[pino_summa].first) {
        string ohjelma;
        for (int i = 0; i < k; i++) {
            ohjelma += komennot[i];
        }
        for (int i = 0; i < pino_i; i++) {
            ohjelma += PLUS;
        }
        ohjelma.resize(ohjelma.size() - 1);
        ohjelmat[pino_summa] = {k + pino_i, ohjelma};
        tulosta(pino_summa, k + pino_i, ohjelma);
    }

    int &a = pino[pino_i], &b = pino[pino_i-1], &c = pino[pino_i-2];
    int vanha_summa = pino_summa;
    int vanhat[3] = {a, b, c};
    int vanha_i = pino_i;

    auto palauta = [&]() {
        pino_summa = vanha_summa;
        pino_i = vanha_i;
        a = vanhat[0];
        b = vanhat[1];
        c = vanhat[2];
    };

    // +
    auto do_PLUS = [&]() {
    if (b && a + b <= tulos_max) {
        b = a + b;
        pino_i--;
        komennot[k] = PLUS;
        dfs(k + 1);
        palauta();
    }
    };

    // *
    auto do_MUL = [&]() {
    if (b && (long)a * b <= tulos_max) {
        pino_summa -= a + b;
        b = a * b;
        pino_i--;
        pino_summa += b;
        komennot[k] = MUL;
        dfs(k + 1);
        palauta();
    }
    };

    // ROT
    auto do_ROT = [&]() {
    if (c && (komennot[k-1] != ROT || komennot[k-2] != ROT)) {
        int tmp = c;
        c = b;
        b = a;
        a = tmp;
        komennot[k] = ROT;
        dfs(k + 1);
        palauta();
    }
    };

    // SWAP
    auto do_SWAP = [&]() {
    if (b && komennot[k-1] != SWAP) {
        swap(a, b);
        komennot[k] = SWAP;
        dfs(k + 1);
        palauta();
    }
    };

    // DUP
    auto do_DUP = [&]() {
    if (pino_i < pino_max) {
        pino_i++;
        pino[pino_i] = a;
        pino_summa += a;
        komennot[k] = DUP;
        dfs(k + 1);
        palauta();
    }
    };

    // OVER
    auto do_OVER = [&]() {
    if (b && pino_i < pino_max) {
        pino_i++;
        pino[pino_i] = b;
        pino_summa += b;
        komennot[k] = OVER;
        dfs(k + 1);
        palauta();
    }
    };

    do_PLUS();
    do_MUL();
    do_OVER();
    do_SWAP();
    do_ROT();
    do_DUP();
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int j;
        cin >> j;
        ohjelmat[j] = {komennot_max + 1, ""};
    }
    dfs(0);
}

Test 1

Verdict: WRONG ANSWER