| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 536537 |
2022-03-13T13:39:56 Z |
idas |
ASM (LMIO18_asm) |
C++11 |
|
1 ms |
212 KB |
#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr)
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define all(x) (x).begin(), (x).end()
#define le(vec) vec[vec.size()-1]
#define sz(x) ((int)((x).size()))
#define pb push_back
#define s second
#define f first
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
const int INF=1e9, MOD=1e9+7, mod=998244353;
const ll LINF=1e13;
void setIO()
{
FAST_IO;
}
void setIO(string s)
{
FAST_IO;
freopen((s+".in").c_str(), "r", stdin);
//freopen((s+".out").c_str(), "w", stdout);
}
#define int long long
const int N=60;
int n;
string a[N], b[N];
vector<pair<string, ll>> ans;
void n1()
{
ll x=stoll(a[0]), y=stoll(b[0]);
if(x>y){
if(y==0){
cout << 2 << "\nmultiply 0" << "\nprint";
}
else cout << 3 << "\nmultiply 0" << "\nadd " << y << "\nprint";
}
else if(x==y){
cout << 1 << "\nprint";
}
else{
cout << 2 << "\nadd " << y-x << "\nprint";
}
}
bool valid(vector<string> &sq)
{
ll lst=-1;
for(auto x : sq){
if(stoll(x)<lst) return false;
lst=stoll(x);
}
return true;
}
vector<pair<string, ll>> get(vector<string> up, vector<string> down)
{
vector<pair<string, ll>> ret;
FOR(i, 1, sz(up))
{
ll x=stoll(up[i-1]), y=stoll(up[i]), z=stoll(down[i-1]), w=stoll(down[i]);
if(x-z==0 || (y-w)%(x-z)!=0 || x-z>y-w) return vector<pair<string, ll>>({});
ll a=(y-w)/(x-z), b=y-x*a;
if(b<0 || a<0 || a>ll(1e18) || b>ll(1e18)) return vector<pair<string, ll>>({});
if(a!=1){
ret.pb({"multiply", a});
}
if(b!=0){
ret.pb({"add", b});
}
ret.pb({"print", 0});
}
return ret;
}
bool can(vector<pair<string, ll>> ord)
{
FOR(i, 2, n)
{
ll now=stoll(a[i]);
int in=0; string num="";
for(auto it : ord){
if(it.f=="multiply"){
now*=it.s;
if(now<0) return false;
}
else if(it.f=="add"){
now+=it.s;
if(now<0) return false;
}
else{
if(now==0) continue;
bool fnd=false;
while(in<sz(b[i])){
num+=b[i][in]; in++;
if(stoll(num)==now){
fnd=true;
break;
}
}
if(!fnd){
return false;
}
num="";
}
}
}
return true;
}
vector<string> up;
void rec2(int in, int d, vector<string> &sq)
{
if(in==sz(b[1])){
if(valid(sq)){
vector<string> new_up=up;
if(sz(sq)!=sz(new_up)){
while(sz(sq)<sz(new_up)){
sq.insert(sq.begin(), "0");
}
while(sz(sq)>sz(new_up)){
new_up.insert(new_up.begin(), "0");
}
}
vector<pair<string, ll>> ord=get(new_up, sq);
if(!ord.empty() && can(ord)){
if(ans.empty() || sz(ord)<sz(ans)){
ans=ord;
}
}
}
return;
}
int nxtin=in+d;
string nxt=b[1].substr(in, d);
while(true){
if(nxtin>sz(b[1])) break;
vector<string> tmp=sq; tmp.pb(nxt);
rec2(nxtin, d, tmp);
nxt+=b[1][nxtin];
nxtin++;
d++;
}
}
void rec(int in, int d, vector<string> &sq)
{
if(in==sz(b[0])){
if(valid(sq)){
up=sq;
vector<string> mt; mt.pb(a[1]);
rec2(0, 1, mt);
}
return;
}
int nxtin=in+d;
string nxt=b[0].substr(in, d);
while(true){
if(nxtin>sz(b[0])) break;
vector<string> tmp=sq; tmp.pb(nxt);
rec(nxtin, d, tmp);
nxt+=b[0][nxtin];
nxtin++;
d++;
}
}
signed main()
{
//setIO("asm-vyr.81-4");
setIO();;
cin >> n;
FOR(i, 0, n) cin >> a[i] >> b[i];
bool eq=true;
FOR(i, 1, n)
{
if(b[i]!=b[0]){
eq=false;
break;
}
}
if(n==1){
n1();
return 0;
}
if(eq){
cout << "3\nmultiply 0\nadd " << b[0] << "\nprint";
return 0;
}
vector<string> mt; mt.pb(a[0]);
rec(0, 1, mt);
if(sz(ans)==0){
cout << -1;
return 0;
}
cout << sz(ans) << '\n';
for(auto it : ans){
if(it.f=="print"){
cout << it.f << '\n';
}
else{
cout << it.f << " " << it.s << '\n';
}
}
}
/*
4
1 365455
2 698182
3 912108109
0 32728
8
multiply 3
print
add 3
print
multiply 9
print
add 1
print
2
62 3
3 3
3
multiply 0
add 3
print
6
1 13
2 23
3 33
4 43
5 53
0 3
3
multiply 10
add 3
print
*/
Compilation message
asm.cpp: In function 'void setIO(std::string)':
asm.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | freopen((s+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
