Submission #254009

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
254009	2020-07-29T09:08:00 Z	VEGAnn	Slon (COCI15_slon)	C++14	120 / 120	2 ms	640 KB

slon

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define i2 array<int,2>
#define sz(x) ((int)x.size())
#define pap pair<i2, int>
#define ft first
#define sd second
using namespace std;
typedef long long ll;
const int N = 2010;
const int oo = 2e9;
string s;
int p, m, glob_md;

int mult(int x, int y) { return (1ll * x * y) % m; }

int sum(int x, int y){
    return (x + y) % m;
}

int sub(int x, int y){
    return (x - y + m) % m;
}

// add last poly after all calculations

pap calc(int lf){
    i2 res = {0, 0};
    i2 last = {0, 0};

    lf++;

    if (s[lf] == '('){
        pap nw = calc(lf);

        lf = nw.sd + 1;
        last = nw.ft;
    } else {
        if (s[lf] == 'x'){
            lf++;
            last[1] = sum(last[1], 1);
        } else {
            while (s[lf] >= '0' && s[lf] <= '9'){
                last[0] = mult(last[0], 10);
                last[0] = sum(last[0], (s[lf] - '0'));
                lf++;
            }
        }
    }

    //cerr << last[0] << " " << last[1] << '\n';

    while (s[lf] != ')'){
        if (s[lf] == '+'){
            res[0] = sum(res[0], last[0]);
            res[1] = sum(res[1], last[1]);

            last = {0, 0};

            lf++;

            if (s[lf] == '('){
                pap nw = calc(lf);

                lf = nw.sd + 1;
                last = nw.ft;

                //cerr << last[0] << " " << last[1] << '\n';
            } else {
                if (s[lf] == 'x'){
                    lf++;
                    last[1] = sum(last[1], 1);
                } else {
                    while (s[lf] >= '0' && s[lf] <= '9'){
                        last[0] = mult(last[0], 10);
                        last[0] = sum(last[0], (s[lf] - '0'));
                        lf++;
                    }
                }
            }
        } else if (s[lf] == '-'){
            res[0] = sum(res[0], last[0]);
            res[1] = sum(res[1], last[1]);

            last = {0, 0};

            lf++;

            if (s[lf] == '('){
                pap nw = calc(lf);

                lf = nw.sd + 1;
                last = nw.ft;

                //cerr << last[0] << " " << last[1] << '\n';
            } else {
                if (s[lf] == 'x'){
                    lf++;
                    last[1] = sum(last[1], 1);
                } else {
                    while (s[lf] >= '0' && s[lf] <= '9'){
                        last[0] = mult(last[0], 10);
                        last[0] = sum(last[0], (s[lf] - '0'));
                        lf++;
                    }
                }
            }

            last[0] = mult(m - 1, last[0]);
            last[1] = mult(m - 1, last[1]);
        } else {
            i2 Last = {0, 0};

            lf++;

            if (s[lf] == '('){
                pap nw = calc(lf);

                lf = nw.sd + 1;
                Last = nw.ft;

                //cerr << Last[0] << " " << Last[1] << '\n';
            } else {
                if (s[lf] == 'x'){
                    lf++;
                    Last[1] = sum(Last[1], 1);
                } else {
                    while (s[lf] >= '0' && s[lf] <= '9'){
                        Last[0] = mult(Last[0], 10);
                        Last[0] = sum(Last[0], (s[lf] - '0'));
                        lf++;
                    }
                }
            }

            last[1] = sum(mult(last[0], Last[1]),
                          mult(last[1], Last[0]));
            last[0] = mult(last[0], Last[0]);

            //cerr << mult(last[0], Last[1]) << '\n';
            //cerr << mult(last[1], Last[0]) << '\n';

            //cerr << last[0] << " " << last[1] << '\n';
        }
    }

    res[0] = sum(res[0], last[0]);
    res[1] = sum(last[1], res[1]);

    //cerr << res[0] << " " << res[1] << '\n';

    return MP(res, lf);
}

void euclid(int a, int b, int &x, int &y){
    if (b == 0){
        x = 1;
        y = 0;
        return;
    }

    int xx, yy;

    euclid(b, a % b, xx, yy);

    x = yy;
    y = (0ll + xx - ((1ll * (a / b) * yy) % glob_md) + glob_md) % glob_md;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> s >> p >> m;

    s = "(" + s + ")";

    //cerr << s << '\n';

    i2 res = calc(0).ft;

//    cerr << res[0] << " " << res[1] << '\n';

    p = sub(p, res[0]);

    int gc = __gcd(res[1], m);

    assert(p % gc == 0);

    glob_md = m / gc;

    p /= gc;
    res[1] /= gc;

    int xx, yy;

    euclid(res[1], glob_md, xx, yy);

    cout << (1ll * p * xx) % glob_md;

    return 0;
}

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	2 ms	640 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	512 KB	Output is correct
10	Correct	1 ms	516 KB	Output is correct