Submission #374113

#TimeUsernameProblemLanguageResultExecution timeMemory
374113gustasonASM (LMIO18_asm)C++11
9 / 100
1 ms512 KiB
#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); return stoll(s); } bool check(vector<pair<char, int>> ans) { vector<int> last(n+1, -1); for(int i = 0; i < n; i++) { ll x = a[i].first; string s = to_string(a[i].second); s += "xyz"; 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); // cout << x << " " << last[i] << "\n"; int lg = ceil(log10(x)); if (lg + last[i] > n+2) return false; for(int k = 1; k <= lg; k++) { // cout << s[last[i]+k] << " " << st[k-1] << "\n"; if (s[last[i]+k] != st[k-1]) return false; } last[i] += lg; } if (x > a[i].second) return false; } // cout << last[i] << "\n"; if (last[i] != s.size()-4) 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;}); 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; ll curra = a[0].first, currb = a[1].first; pair<int, int> last = {-1, -1}; vector<pair<char, int>> ins; 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]); 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 && k != 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}); curra *= got.first; curra += got.second; currb *= got.first; currb += got.second; // cout << curra << " " << currb << "\n"; } // cerr << "\n"; if (ins.size() < best && check(ins)) { best = ins.size(); ans = ins; } } } 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 (stderr)

asm.cpp: In function 'bool check(std::vector<std::pair<char, long long int> >)':
asm.cpp:40:21: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if (last[i] != s.size()-4) return false;
asm.cpp: In function 'void solve()':
asm.cpp:129: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]
  129 |             for(int k = 0; k < i.size(); k++) {
      |                            ~~^~~~~~~~~~
asm.cpp:150: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]
  150 |             if (ins.size() < best && check(ins)) {
      |                 ~~~~~~~~~~~^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...