oj.uz

Submission #256491

# Submission time Handle Problem Language Result Execution time Memory
256491 2020-08-02T18:37:28 Z Vimmer Slon (COCI15_slon) C++14
120 / 120
 2 ms 640 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define pf push_front
#define N 100050
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef short int si;
typedef array <ll, 3> a3;
typedef array <ll, 5> a5;

//typedef tree <ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

string a;

ll p, m;

ll sm(ll x, ll y) {return (x + y + m) % m;}
ll mult(ll x, ll y) {return (x * y) % m;}

bool gd(ll x) {return a[x] != '+' && a[x] != '-' && a[x] != '*' && a[x] != '(' && a[x] != ')';}

ll get_num(ll &i)
{
    ll num = 0, j = 0;

    while (i + j + 1 < sz(a) && gd(i + j + 1)) j++;

    for (ll u = i; u <= i + j; u++) {num *= 10; num += a[u] - '0'; num = sm(num, 0);}

    if (j == 0 && a[i + j] == 'x') num = -1;

    i += j + 1;

    return num;
}

pair <pair <ll, ll>, ll>  calc(ll v);

pair <ll, ll> get_mult(ll fr, ll sc, ll &i)
{
    vector <pair <ll, ll> > gr; gr.clear();

    gr.pb({fr, sc});

    for(;; i++)
    {
        if (a[i] == '(')
        {
            pair <pair <ll, ll>, ll> pt = calc(i);

            gr.pb(pt.F);

            i = pt.S;
        }
        else
        {
            ll num = get_num(i);

            if (num == -1) gr.pb({0, 1}); else gr.pb({num, 0});
        }

        if (a[i] == '*') continue;

        break;
    }

    ll x = 0, db = 0;

    for (auto it : gr)
        if (it.S != 0) {x = it.S; if (it.F != 0) db = it.F;}

    ll cur = 1;

    for (auto it : gr)
    {
        if (it.S != 0) continue;

        cur = mult(cur, it.F);
    }

    if (x == 0) db = 1;

    return {mult(cur, db), mult(x, cur)};
}

pair <pair <ll, ll>, ll>  calc(ll v)
{
    ll kf = 0, val = 0, otr = 1;

    for (ll i = v + 1; i < sz(a); i++)
    {
        ll fr = 0, sc = 0;

        if (a[i] == ')') return {{val, kf}, i + 1};

        if (a[i] == '+') {otr = 1; continue;}

        if (a[i] == '-') {otr = -1; continue;}

        if (a[i] == '(')
        {
            pair <pair <ll, ll>, ll> pt = calc(i);

            i = pt.S;

            if (a[i] != '*')
            {
                val = sm(val, mult(otr, pt.F.F));

                kf = sm(kf, mult(otr, pt.F.S));

                i--;

                continue;
            }
            else {fr = pt.F.F; sc = pt.F.S;}
        }
        else
        {
            ll num = get_num(i);

            if (a[i] != '*')
            {
                if (num != -1) val = sm(val, mult(otr, num)); else kf = sm(kf, otr);

                i--;

                continue;
            }

            if (num == -1) fr = 1; else sc = num;
        }

        i++;

        pair <ll, ll> tr = get_mult(fr, sc, i);

        kf = sm(kf, mult(otr, tr.S));

        val = sm(val, mult(otr, tr.F));

        i--;
    }
}

void gcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;

        y = 0;

        return;

    }

    ll X, Y;

    gcd(b, a % b, X, Y);

    x = Y;

    y = (X - (a / b) * Y + m) % m;
}
int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> a;

    cin >> p >> m;

    a = '(' + a;

    a = a + ')';

    pair <pair <ll, ll>, ll> pt = calc(0);

    ll val = pt.F.F, kf = pt.F.S;

    //cout << val << " " << kf << endl;

    p -= val;

    p = sm(p, m);

    ll gc = __gcd(m, kf);

    m /= gc;

    p /= gc;

    kf /= gc;

    ll x, y;

    gcd(kf, m, x, y);

    cout << (ll(1e9) * m + sm(0, mult(p, x))) % m << endl;
}

Compilation message

slon.cpp: In function 'std::pair<std::pair<long long int, long long int>, long long int> calc(ll)':
slon.cpp:163:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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 636 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 640 KB Output is correct