oj.uz

Submission #198170

# Submission time Handle Problem Language Result Execution time Memory
198170 2020-01-25T02:16:40 Z model_code ASM (LMIO18_asm) C++14
100 / 100
 10 ms 380 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 1 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 0 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 256 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 0 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 7 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 252 KB Output is correct
18 Correct 6 ms 376 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 380 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 380 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 0 ms 380 KB Output is correct
36 Correct 2 ms 376 KB Output is correct
37 Correct 2 ms 376 KB Output is correct
38 Correct 2 ms 376 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 2 ms 376 KB Output is correct
41 Correct 5 ms 376 KB Output is correct
42 Correct 2 ms 376 KB Output is correct
43 Correct 2 ms 256 KB Output is correct
44 Correct 2 ms 252 KB Output is correct
45 Correct 2 ms 376 KB Output is correct
46 Correct 2 ms 256 KB Output is correct
47 Correct 2 ms 376 KB Output is correct
48 Correct 2 ms 376 KB Output is correct
49 Correct 1 ms 376 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 3 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 9 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 380 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 10 ms 376 KB Output is correct
28 Correct 3 ms 376 KB Output is correct
29 Correct 3 ms 376 KB Output is correct
30 Correct 1 ms 376 KB Output is correct
31 Correct 3 ms 376 KB Output is correct
32 Correct 2 ms 256 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 256 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 376 KB Output is correct
37 Correct 2 ms 376 KB Output is correct
38 Correct 2 ms 252 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 2 ms 376 KB Output is correct
41 Correct 0 ms 376 KB Output is correct
42 Correct 2 ms 376 KB Output is correct
43 Correct 2 ms 376 KB Output is correct
44 Correct 2 ms 376 KB Output is correct
45 Correct 2 ms 376 KB Output is correct
46 Correct 7 ms 376 KB Output is correct
47 Correct 2 ms 376 KB Output is correct
48 Correct 2 ms 252 KB Output is correct
49 Correct 6 ms 376 KB Output is correct
50 Correct 2 ms 256 KB Output is correct
51 Correct 2 ms 380 KB Output is correct
52 Correct 2 ms 376 KB Output is correct
53 Correct 2 ms 348 KB Output is correct
54 Correct 2 ms 376 KB Output is correct
55 Correct 2 ms 376 KB Output is correct
56 Correct 2 ms 376 KB Output is correct
57 Correct 2 ms 376 KB Output is correct
58 Correct 2 ms 380 KB Output is correct
59 Correct 2 ms 376 KB Output is correct
60 Correct 2 ms 376 KB Output is correct
61 Correct 2 ms 376 KB Output is correct
62 Correct 2 ms 376 KB Output is correct
63 Correct 2 ms 376 KB Output is correct
64 Correct 2 ms 376 KB Output is correct
65 Correct 2 ms 376 KB Output is correct
66 Correct 0 ms 380 KB Output is correct
67 Correct 2 ms 376 KB Output is correct
68 Correct 2 ms 376 KB Output is correct
69 Correct 2 ms 376 KB Output is correct
70 Correct 2 ms 376 KB Output is correct
71 Correct 2 ms 376 KB Output is correct
72 Correct 5 ms 376 KB Output is correct
73 Correct 2 ms 376 KB Output is correct
74 Correct 2 ms 256 KB Output is correct
75 Correct 2 ms 252 KB Output is correct
76 Correct 2 ms 376 KB Output is correct
77 Correct 2 ms 256 KB Output is correct
78 Correct 2 ms 376 KB Output is correct
79 Correct 2 ms 376 KB Output is correct
80 Correct 1 ms 376 KB Output is correct
81 Correct 2 ms 376 KB Output is correct
82 Correct 2 ms 376 KB Output is correct
83 Correct 2 ms 256 KB Output is correct
84 Correct 2 ms 256 KB Output is correct
85 Correct 2 ms 376 KB Output is correct
86 Correct 2 ms 376 KB Output is correct