Ohjelmat

#include <algorithm>
#include <atomic>
#include <iostream>
#include <mutex>
#include <thread>
#include <tuple>
#include <vector>

using namespace std;

constexpr int M = 1000000;

struct Tila {
    vector<const char*> ohjelma;
    vector<int> pino;
    int maxPituus;
};

thread_local vector<const char*> saieOhjelmat[M];
vector<const char*> ohjelmat[M];

mutex kommaMutex;
void kommaa() {
    lock_guard kommaLukko(kommaMutex);
    for(int i = 1; i < M; ++i) {
        if(!saieOhjelmat[i].empty() && (ohjelmat[i].empty() || saieOhjelmat[i].size() < ohjelmat[i].size())) {
            ohjelmat[i] = saieOhjelmat[i];
        }
    }
}

vector<Tila> tyot;

void hae(Tila& tila, int syv) {
    int p = tila.pino.size();
    if(p - tila.maxPituus > 1) {
        return;
    }
    if(p == 0) throw 5;
    if(syv == 0) {
        tyot.push_back(tila);
        return;
    }
    if(p == 1) {
        int x = tila.pino[0];
        if(x < 0 || x >= M) throw 5;
        if(saieOhjelmat[x].empty() || tila.ohjelma.size() < saieOhjelmat[x].size()) {
            saieOhjelmat[x] = tila.ohjelma;
        }
    }
    if(tila.maxPituus == 0) return;
    --tila.maxPituus;
    if(tila.pino.size() >= 2 && tila.pino[p - 2] + tila.pino[p - 1] < M) {
        int a = tila.pino.back();
        tila.pino.pop_back();
        int b = tila.pino.back();
        tila.pino.pop_back();
        tila.pino.push_back(a + b);
        tila.ohjelma.push_back("+");
        hae(tila, syv - 1);
        tila.ohjelma.pop_back();
        tila.pino.pop_back();
        tila.pino.push_back(b);
        tila.pino.push_back(a);
    }
    if(tila.pino.size() >= 2 && (long long int)tila.pino[p - 2] * (long long int)tila.pino[p - 1] < (long long int)M) {
        int a = tila.pino.back();
        tila.pino.pop_back();
        int b = tila.pino.back();
        tila.pino.pop_back();
        tila.pino.push_back(a * b);
        tila.ohjelma.push_back("*");
        hae(tila, syv - 1);
        tila.ohjelma.pop_back();
        tila.pino.pop_back();
        tila.pino.push_back(b);
        tila.pino.push_back(a);
    }
    if(tila.pino.size() >= 2) {
        swap(tila.pino[p - 1], tila.pino[p - 2]);
        tila.ohjelma.push_back("SWAP");
        hae(tila, syv - 1);
        tila.ohjelma.pop_back();
        swap(tila.pino[p - 1], tila.pino[p - 2]);
    }
    {
        tila.pino.push_back(tila.pino.back());
        tila.ohjelma.push_back("DUP");
        hae(tila, syv - 1);
        tila.ohjelma.pop_back();
        tila.pino.pop_back();
    }
    if(tila.pino.size() >= 2) {
        tila.pino.push_back(tila.pino[p - 2]);
        tila.ohjelma.push_back("OVER");
        hae(tila, syv - 1);
        tila.ohjelma.pop_back();
        tila.pino.pop_back();
    }
    if(tila.pino.size() >= 3) {
        tie(tila.pino[p - 3], tila.pino[p - 2], tila.pino[p - 1]) = tuple(tila.pino[p - 2], tila.pino[p - 1], tila.pino[p - 3]);
        tila.ohjelma.push_back("ROT");
        hae(tila, syv - 1);
        tila.ohjelma.pop_back();
        tie(tila.pino[p - 3], tila.pino[p - 2], tila.pino[p - 1]) = tuple(tila.pino[p - 1], tila.pino[p - 3], tila.pino[p - 2]);
    }
    ++tila.maxPituus;
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);

    Tila tila;
    tila.pino.push_back(1);
    tila.maxPituus = 24;
    hae(tila, 12);
    kommaa();

    cerr << tyot.size() << "\n";
    sort(tyot.begin(), tyot.end(), [&](const Tila& a, const Tila& b) { return a.pino < b.pino; });
    tyot.erase(unique(tyot.begin(), tyot.end(), [&](const Tila& a, const Tila& b) { return a.pino == b.pino; }), tyot.end());
    cerr << tyot.size() << "\n";

    vector<thread> saikeet;
    atomic<int> seuraavaTyoIdx = 0;
    for(int si = 0; si < 8; ++si) {
        saikeet.emplace_back([&]() {
            while(true) {
                int tyoIdx = seuraavaTyoIdx.fetch_add(1, memory_order_relaxed);
                if(tyoIdx >= (int)tyot.size()) {
                    break;
                }
                Tila tyo = move(tyot[tyoIdx]);
                hae(tyo, -1);
            }
            kommaa();
            cerr << "LOPPU\n";
        });
    }
    for(thread& saie : saikeet) {
        saie.join();
    }

    for(int i = 0; i < 5; ++i) {
        vector<int> loydetyt;
        for(int i = 0; i < M; ++i) {
            if(!ohjelmat[i].empty()) {
                loydetyt.push_back(i);
            }
        }
        for(int x = 1; x < M; ++x) {
            if(ohjelmat[x].empty()) {
                for(int a : loydetyt) {
                    {
                        int b = x - a;
                        if(b >= 1 && b < M && !ohjelmat[b].empty()) {
                            int l = (int)(ohjelmat[a].size() + ohjelmat[b].size()) + 3;
                                if(ohjelmat[x].empty() || l < (int)ohjelmat[x].size()) {
                                vector<const char*> ohjelma;
                                ohjelma.push_back("DUP");
                                ohjelma.insert(ohjelma.end(), ohjelmat[a].begin(), ohjelmat[a].end());
                                ohjelma.push_back("SWAP");
                                ohjelma.insert(ohjelma.end(), ohjelmat[b].begin(), ohjelmat[b].end());
                                ohjelma.push_back("+");
                                if((int)ohjelma.size() != l) throw 5;
                                ohjelmat[x] = ohjelma;
                            }
                        }
                    }
                    if(x % a == 0) {
                        int b = x / a;
                        if(b >= 1 && b < M && !ohjelmat[b].empty()) {
                            int l = (int)(ohjelmat[a].size() + ohjelmat[b].size()) + 3;
                                if(ohjelmat[x].empty() || l < (int)ohjelmat[x].size()) {
                                vector<const char*> ohjelma;
                                ohjelma.push_back("DUP");
                                ohjelma.insert(ohjelma.end(), ohjelmat[a].begin(), ohjelmat[a].end());
                                ohjelma.push_back("SWAP");
                                ohjelma.insert(ohjelma.end(), ohjelmat[b].begin(), ohjelmat[b].end());
                                ohjelma.push_back("*");
                                if((int)ohjelma.size() != l) throw 5;
                                ohjelmat[x] = ohjelma;
                            }
                        }
                    }
                }
            }
        }
    }

    int pituus = 0;

    int tc;
    cin >> tc;
    for(int ti = 0; ti < tc; ++ti) {
        int x;
        cin >> x;

        if(ohjelmat[x].empty()) {
            cerr << "OHJELMA " << x << " PUUTTUU\n";
            throw 5;
        }

        cout << ohjelmat[x].size() << "\n";
        for(const char* kasky : ohjelmat[x]) {
            cout << kasky << " ";
        }
        cout << "\n";
        pituus += (int)ohjelmat[x].size();
    }

    cerr << "PITUUS: " << pituus << "\n";

    return 0;
}

Test 1

Verdict: WRONG ANSWER