Submission #536491

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
536491	2022-03-13T12:21:39 Z	idas	ASM (LMIO18_asm)	C++11	9 / 100	1 ms	468 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);
}

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]);

        //assert(x-z!=0);
        //assert((y-w)%(x-z)==0);
        if(x-z==0 || (y-w)%(x-z)!=0) return vector<pair<string, ll>>({});
        ll a=(y-w)/(x-z), b=y-x*a;
        if(b<0 || a<0) 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;
            }
            else if(it.f=="add"){
                now+=it.s;
            }
            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)){
            if(sz(sq)!=sz(up)){
                while(sz(sq)<sz(up)){
                    sq.insert(sq.begin(), "0");
                }
                while(sz(sq)>sz(up)){
                    up.insert(up.begin(), "0");
                }
            }

//            for(auto x : up){
//                cout << x << " ";
//            }
//            cout << '\n';
//            for(auto x : sq){
//                cout << x << " ";
//            }
//            cout << '\n';

            vector<pair<string, ll>> ord=get(up, sq);
//            for(auto x : ord){
//                cout << x.f << " " << x.s << '\n';
//            }
//            cout << "\n";

            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)){
//            for(auto x : sq){
//                cout << x << " ";
//            }
//            cout << '\n';
            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++;
    }
}

int main()
{
    setIO();
    cin >> n;
    FOR(i, 0, n) cin >> a[i] >> b[i];

    if(n==1){
        n1();
        return 0;
    }

    vector<string> mt; mt.pb(a[0]);
    rec(0, 1, mt);

//    vector<pair<string, ll>> ord={
//        {"multiply", 3},
//        {"print", 0},
//        {"add", 3},
//        {"print", 0}
//    };
//
//    cout << can(ord);

    if(sz(ans)==0){
        assert("sus"=="red");
        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
*/

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from asm.cpp:1:
asm.cpp: In function 'int main()':
asm.cpp:226:21: warning: comparison with string literal results in unspecified behavior [-Waddress]
  226 |         assert("sus"=="red");
      |                ~~~~~^~~~~~~
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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
asm.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct
6	Correct	212 KB	Output is correct
7	Correct	212 KB	Output is correct
8	Correct	212 KB	Output is correct
9	Correct	212 KB	Output is correct
10	Correct	212 KB	Output is correct
11	Correct	212 KB	Output is correct
12	Correct	212 KB	Output is correct
13	Correct	212 KB	Output is correct
14	Correct	212 KB	Output is correct
15	Correct	212 KB	Output is correct
16	Correct	212 KB	Output is correct

Subtask #2
0 / 17.0

#	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	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Runtime error	1 ms	468 KB	Execution killed with signal 6
7	Halted	0 ms	0 KB	-

Subtask #3
0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	1 ms	468 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	1 ms	468 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Submission #536491

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 17.0

Subtask #3 0 / 53.0

Subtask #4 0 / 21.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 17.0

Subtask #3
0 / 53.0

Subtask #4
0 / 21.0