oj.uz

Submission #374165

# Submission time Handle Problem Language Result Execution time Memory
374165 2021-03-06T19:18:23 Z gustason ASM (LMIO18_asm) C++14
79 / 100
 1000 ms 748 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
ll INF = 1LL << 62;
int n;
vector<pair<ll, ll>> a;
ll subll(ll x, int l, int r) {
    string s = to_string(x);
    s = s.substr(l, (r-l)+1);
    if (s.empty()) return -1;
    return stoll(s);
}
bool check(vector<pair<char, int>> ans) {
    string str[n+1];
    for(int i = 0; i < n; i++) {
        ll x = a[i].first;
        string s = to_string(a[i].second);

        for(auto j : ans) {
            if (j.first == 'm') {
                x *= j.second;
            } else if (j.first == 'a') {
                x += j.second;
            } else {
                string st = to_string(x);
                str[i] += st;
            }
            if (x > a[i].second) return false;
        }
//        cout << last[i] << "\n";
        if (str[i] != s) return false;
    }
//    cerr << "\n";
    return true;
}
pair<ll, ll> checkpair(pair<ll, ll> x, pair<ll, ll> y) {
    ll diff1 = y.first - x.first;
    ll diff2 = y.second - x.second;
    if (diff1 < 0) return {-1, -1};
    if (diff2 < 0) return {-1, -1};

    if (diff2 == 0) diff2++;
    ll mult = (diff2) / (diff1);
    if (mult == 0) {
        if (x.second != y.second)
            return {-1, -1};
        else
            return {0, x.second};
    }
    if (INF / mult < x.first) return {-1, -1};

    ll add = x.second - (x.first * mult);
    return {mult, add};
}
void printAns(vector<pair<char, ll>> ans) {
    cout << ans.size() << "\n";
    for(auto i : ans) {
        if (i.first == 'm') {
            cout << "multiply " << i.second;
        } else if (i.first == 'a') {
            cout << "add " << i.second;
        } else {
            cout << "print";
        }
        cout << "\n";
    }
    exit(0);
}
void solveOne(ll x, ll y) {
    vector<pair<char, int>> ans;
    if (x > y) {
        ans.push_back({'m', 0});
        x = 0;
    }
    if (y - x != 0)
        ans.push_back({'a', y - x});
    ans.push_back({'p', -1});
    printAns(ans);
}
vector<vector<int>> split(int na) {
    vector<vector<int>> splita;
    for(int mask = 0; mask < (1 << na); mask++) {
        int last = 0, lastl = 0;
        vector<int> idx;
        for(int i = 0; i < na; i++) {
            if (mask & (1 << i)) {
                if (i - last < lastl)
                    goto Done;
                idx.push_back(i);
                lastl = i - last;
                last = i;
            }
        }
        if (idx.empty() || idx.back() != na-1)
            idx.push_back(na-1);
        splita.push_back(idx);
        Done:;
    }
    return splita;
}
void solve() {
    if (n == 1)
        solveOne(a[0].first, a[0].second);
    sort(a.begin(), a.end(), [](pair<ll, ll>& left, pair<ll, ll>& right){return left.second < right.second;});

    vector<pair<char, int>> same;
    same.push_back({'m', 0});
    if (a[0].second != 0)
        same.push_back({'a', a[0].second});
    same.push_back({'p', -1});
    if (check(same)) {
        printAns(same);
    }

    int na = ceil(log10(a[0].second));
    int nb = ceil(log10(a[1].second));
    int best = 999;
    vector<pair<char, int>> ans;
    vector<vector<int>> splita = split(na),
                        splitb = split(nb);

    for(auto i : splita) {
        for(auto j : splitb) {
            if (i.size() != j.size()) continue;
//            if (i.size() == 4) {
//            for(int ii : i) {
//                cout << ii << " ";
//            } cout << "\n";
//            for(int jj : j) {
//                cout << jj << " ";
//            } cout << "\n";
//            }
            ll curra = a[0].first, currb = a[1].first;
            pair<int, int> last = {-1, -1};
            vector<pair<char, int>> ins;
//            vector<int> vx = {0, 1, 3, 6};
//            vector<int> vy = {1, 3, 6, 9};
//            if (i != vx || j != vy) continue;
            for(int k = 0; k < i.size(); k++) {
                ll x = subll(a[0].second, last.first+1, i[k]);
                ll y = subll(a[1].second, last.second+1, j[k]);
                if (x == -1 || y == -1) break;

                last = {i[k], j[k]};
//                cout << x << " " << y << "\n";
                pair<ll, ll> got = checkpair({curra, x}, {currb, y});
                if (got.first == -1) continue;
                if (got.first == 0) break;
                if (got.first != 1) ins.push_back({'m', got.first});
                if (got.second != 0)
                    ins.push_back({'a', got.second});
                ins.push_back({'p', -1});
//                cout << curra << " " << currb << " " << got.first << " " << got.second << " " << x << " " << y << " " << i[k] << " " << j[k] << "\n";
                curra *= got.first;
                curra += got.second;
                currb *= got.first;
                currb += got.second;
//                cout << curra << " " << currb << "\n";
//                cout << curra << " " << currb << " " << got.first << " " << got.second << "\n";
            }
//            cerr << "\n";

            if (ins.size() < best && check(ins)) {
                best = ins.size();
                ans = ins;
                printAns(ans);
            }
        }
   }

   if (best != 999) {
        printAns(ans);
   } else {
        cout << -1;
   }
//    for(auto i : splitb) {
//        cout << i.size() << "\n";
//    }
//    cout << splita.size() << " " << splitb.size() << "\n";
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    a.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    solve();
    return 0;
}

Compilation message

asm.cpp: In function 'void solve()':
asm.cpp:140:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |             for(int k = 0; k < i.size(); k++) {
      |                            ~~^~~~~~~~~~
asm.cpp:164:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<char, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  164 |             if (ins.size() < best && check(ins)) {
      |                 ~~~~~~~~~~~^~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
53.0 / 53.0

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

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 3 ms 364 KB Output is correct
15 Correct 3 ms 364 KB Output is correct
16 Correct 3 ms 492 KB Output is correct
17 Correct 5 ms 364 KB Output is correct
18 Correct 7 ms 364 KB Output is correct
19 Correct 3 ms 364 KB Output is correct
20 Correct 2 ms 364 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 376 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 0 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 364 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 1 ms 364 KB Output is correct
38 Correct 1 ms 364 KB Output is correct
39 Correct 1 ms 364 KB Output is correct
40 Correct 1 ms 364 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 1 ms 364 KB Output is correct
43 Correct 0 ms 364 KB Output is correct
44 Correct 1 ms 364 KB Output is correct
45 Correct 1 ms 364 KB Output is correct
46 Correct 1 ms 364 KB Output is correct
47 Correct 1 ms 384 KB Output is correct
48 Correct 0 ms 364 KB Output is correct
49 Correct 1 ms 364 KB Output is correct
50 Correct 0 ms 364 KB Output is correct
51 Correct 0 ms 364 KB Output is correct
52 Correct 1 ms 364 KB Output is correct
53 Correct 0 ms 364 KB Output is correct
54 Correct 1 ms 364 KB Output is correct
55 Correct 1 ms 364 KB Output is correct
56 Execution timed out 1092 ms 748 KB Time limit exceeded
57 Halted 0 ms 0 KB -