Submission #198170

#	Time	Username	Problem	Language	Result	Execution time	Memory
198170		model_code	ASM (LMIO18_asm)	C++14	100 / 100	10 ms	380 KiB

asm

#include <iostream>
#include <fstream>
#include <cstdio>
#include <string>
#include <list>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
#define fori(n) for (int i = 0; i < (n); i++)
#define forj(n) for (int j = 0; j < (n); j++)

const int MAXN = 1000;

const ull MAX_VAL = 1000000000000000000ull;

enum opKind {
    ADD,
    MULTIPLY,
    PRINT,
};

struct op {
    opKind kind;
    ull arg;
};

ull in1, in2;
string outs[2];
vector<op> bestAns;
vector<pull> tests;
vector<op> curProgram;

int starts[2][20];
int partNum[2];

op makeAdd(ull arg) {
    return { ADD, arg };
}

op makeMul(ull arg) {
    return  { MULTIPLY, arg };
}

op makePrint() {
    return { PRINT, 0 };
}

vector<op> solveOne(ull in, ull out) {
    vector<op> ans;
    if (in < out) {
        ans.push_back(makeAdd(out - in));
    } else if (in > out) {
        ans.push_back(makeMul(0));
        if (out > 0) {
            ans.push_back(makeAdd(out));
        }
    }
    ans.push_back(makePrint());
    return ans;
}

void displayNum(ull num, string &to) {
    if (num == 0) {
        to.push_back('0');
    } else if (num < 10) {
        to.push_back('0' + num);
    } else {
        displayNum(num / 10, to);
        to.push_back('0' + (num % 10));
    }
}

ull stringToVal(const string &s, int from, int to) {
    if (from == to) {
        return 0;
    } else {
        return stringToVal(s, from, to - 1) * 10 + (s[to - 1] - '0');
    }
}

bool addStep(ull a, ull b, ull c, ull d) {
    if (a == c) {
        if (d != b) {
            return false;
        }
        if (b > a) {
            curProgram.push_back(makeAdd(b - a));
        } else if (b < a) {
            curProgram.push_back(makeMul(0));
            curProgram.push_back(makeAdd(b));
        }
        curProgram.push_back(makePrint());
        return true;
    }
    ll ct = d - b;
    ll cb = c - a;
    if (ct % cb != 0) {
        return false;
    }
    ll x = ct / cb;
    if (x < 0 || x >= MAX_VAL) return false;
    // check if a*x will overflow
    if ((MAX_VAL * 2 + 10) / a <= x) return false;
    ll y = b - a * x;
    if (y < 0 || y >= MAX_VAL) return false;
    if (x != 1) {
        curProgram.push_back(makeMul(x));
    }
    if (y != 0) {
        curProgram.push_back(makeAdd(y));
    }
    curProgram.push_back(makePrint());
    return true;
}

bool checkProgram() {
    string out = "";
    string expected = "";
    for (int i = 0; i < tests.size(); i++) {
        ull reg = tests[i].first;
        expected.clear();
        out.clear();
        displayNum(tests[i].second, expected);
        for (auto op : curProgram) {
            switch (op.kind) {
            case ADD:
                reg += op.arg;
                break;
            case MULTIPLY:
                reg *= op.arg;
                break;
            case PRINT:
                displayNum(reg, out);
                break;
            }
        }
        if (expected != out) {
            return false;
        }
    }
    return true;
}

void checkPartitions() {
    if (partNum[0] != partNum[1]) {
        return;
    }

    ull values[2][21];
    values[0][0] = in1;
    values[1][0] = in2;
    fori(2) {
        forj(partNum[0]) {
            values[i][j + 1] = stringToVal(outs[i], starts[i][j], starts[i][j + 1]);
        }
    }

    curProgram.clear();
    fori(partNum[0]) {
        if (!addStep(values[0][i], values[0][i + 1], values[1][i], values[1][i + 1])) {
            return;
        }
    }

    if (curProgram.size() < bestAns.size() || bestAns.size() == 0) {
        if (checkProgram()) {
            bestAns = curProgram;
        }
    }
}

int numLen(ull x) {
    if (x < 10) return 1;
    else return 1 + numLen(x / 10);
}

void genPartitions(int t, int num, int minLen) {
    if (starts[t][num] == outs[t].length()) {
        if (t == 0) {
            partNum[0] = num;
            genPartitions(1, 0, numLen(in2));
        } else {
            partNum[1] = num;
            checkPartitions();
        }
    } else {
        for (int start = starts[t][num] + minLen; start <= outs[t].length(); start++) {
            if (outs[t][starts[t][num]] == '0' && start > starts[t][num] + 1)
                continue;
            starts[t][num + 1] = start;
            genPartitions(t, num + 1, start - starts[t][num]);
        }
    }
}

vector<op> solve() {
    if (tests.size() == 1) {
        return solveOne(tests[0].first, tests[0].second);
    }

    bool allSame = true;
    fori(tests.size() - 1) {
        if (tests[i].second != tests[i + 1].second) {
            allSame = false;
            break;
        }
    }

    if (allSame) {
        bestAns.clear();
        bestAns.push_back(makeMul(0));
        if (tests[0].second != 0)
            bestAns.push_back(makeAdd(tests[0].second));
        bestAns.push_back(makePrint());
        return bestAns;
    }

    sort(tests.begin(), tests.end());
    reverse(tests.begin(), tests.end());

    in1 = tests[0].first;
    in2 = tests[1].first;
    fori(2) {
        outs[i].clear();
        displayNum(tests[i].second, outs[i]);
    }

    bestAns.clear();

    starts[0][0] = starts[1][0] = 0;
    genPartitions(0, 0, numLen(in1));
    return bestAns;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
#if defined(_DEBUG) || defined(_RELEASE)
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n;
    cin >> n;
    tests.resize(n);
    fori(n) {
        cin >> tests[i].first >> tests[i].second;
    }
    auto ans = solve();
    if (ans.size() == 0) {
        cout << -1 << endl;
    } else {
        cout << ans.size() << endl;
        for (auto op : ans) {
            switch (op.kind) {
            case ADD:
                cout << "add " << op.arg << endl;
                break;
            case MULTIPLY:
                cout << "multiply " << op.arg << endl;
                break;
            case PRINT:
                cout << "print" << endl;
                break;
            }
        }
    }
}

Compilation message (stderr)

asm.cpp: In function 'bool addStep(ull, ull, ull, ull)':
asm.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (x < 0 || x >= MAX_VAL) return false;
                  ~~^~~~~~~~~~
asm.cpp:110:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ((MAX_VAL * 2 + 10) / a <= x) return false;
         ~~~~~~~~~~~~~~~~~~~~~~~^~~~
asm.cpp:112:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (y < 0 || y >= MAX_VAL) return false;
                  ~~^~~~~~~~~~
asm.cpp: In function 'bool checkProgram()':
asm.cpp:126:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < tests.size(); i++) {
                     ~~^~~~~~~~~~~~~~
asm.cpp: In function 'void genPartitions(int, int, int)':
asm.cpp:185:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (starts[t][num] == outs[t].length()) {
         ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
asm.cpp:194:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int start = starts[t][num] + minLen; start <= outs[t].length(); start++) {
                                                   ~~~~~~^~~~~~~~~~~~~~~~~~~
asm.cpp: In function 'std::vector<op> solve()':
asm.cpp:16:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(n) for (int i = 0; i < (n); i++)
                                 ~~^~~~~
asm.cpp:209:5: note: in expansion of macro 'fori'
     fori(tests.size() - 1) {
     ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 53 / 53
• Subtask 4: 21 / 21