| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 374169 |
2021-03-06T19:37:37 Z |
gustason |
ASM (LMIO18_asm) |
C++14 |
|
1 ms |
364 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);
int cnt = 0;
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) goto Done;
last = {i[k], j[k]};
// cout << x << " " << y << "\n";
pair<ll, ll> got = checkpair({curra, x}, {currb, y});
if (got.first == -1) goto Done;
if (got.first == 0) goto Done;
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;
if (ins.size() < best) goto Done;
// 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);
}
Done:;
}
}
if (best != 999) {
printAns(ans);
} else {
cout << -1;
}
// cout << "\n" << cnt << "\n";
// 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);
// freopen("test.in", "r", stdin);
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:142: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]
142 | for(int k = 0; k < i.size(); k++) {
| ~~^~~~~~~~~~
asm.cpp:161:32: 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]
161 | if (ins.size() < best) goto Done;
| ~~~~~~~~~~~^~~~~~
asm.cpp:166: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]
166 | if (ins.size() < best && check(ins)) {
| ~~~~~~~~~~~^~~~~~
asm.cpp:123:9: warning: unused variable 'cnt' [-Wunused-variable]
123 | int cnt = 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 |
0 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 |
364 KB |
Output is correct |
| 13 |
Correct |
1 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 |
| # |
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 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
