Submission #1313309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313309		the_commando_x	Slon (COCI15_slon)	C++17	120 / 120	1 ms	568 KiB

slon

// #pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;

using pii = pair<int, int>;
using vii = vector<pii>;
using vvii = vector<vii>;

using l = long long;
using vl = vector<l>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;

using pll = pair<l, l>;
using vll = vector<pll>;
using vvll = vector<vll>;

using d = double;
using vd = vector<d>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;

using ld = long double;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;

using vb = vector<bool>;
using vvb = vector<vb>;
using pbb = pair<bool, bool>;
using vbb = vector<pbb>;

#define ff first
#define ss second

#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

void setIO(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (!name.empty())
    {
        (void)freopen((name + ".in").c_str(), "r", stdin);
        (void)freopen((name + ".out").c_str(), "w", stdout);
    }
}

const ld pi = 3.14159265358979323846;

const l LINF = 1e18;
const l INF = 1e9;

const l MOD = 1e9 + 7;
// const l MOD = 998244353;

const l MAXN = 2e5 + 5;

string s;
int ptr;
l M;

/* each expression = (constant, coef_of_x) */
pll parse_expr();

pll parse_factor()
{
    if (s[ptr] == 'x')
    {
        ptr++;
        return {0, 1};
    }

    if (isdigit(s[ptr]))
    {
        l val = 0;
        while (ptr < sz(s) && isdigit(s[ptr]))
        {
            val = (val * 10 + (s[ptr] - '0')) % M;
            ptr++;
        }
        return {val, 0};
    }

    // '(' expr ')'
    ptr++; // '('
    pll res = parse_expr();
    ptr++; // ')'
    return res;
}

pll parse_term()
{
    pll res = parse_factor();
    while (ptr < sz(s) && s[ptr] == '*')
    {
        ptr++;
        pll rhs = parse_factor();
        l c = (res.ff * rhs.ff) % M;
        l x = (res.ff * rhs.ss + res.ss * rhs.ff) % M;
        res = {c, x};
    }
    return res;
}

pll parse_expr()
{
    pll res = parse_term();
    while (ptr < sz(s) && (s[ptr] == '+' || s[ptr] == '-'))
    {
        char op = s[ptr++];
        pll rhs = parse_term();
        if (op == '+')
        {
            res.ff = (res.ff + rhs.ff) % M;
            res.ss = (res.ss + rhs.ss) % M;
        }
        else
        {
            res.ff = (res.ff - rhs.ff + M) % M,
            res.ss = (res.ss - rhs.ss + M) % M;
        }
    }
    return res;
}

l egcd(l a, l b, l &x, l &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    l x1, y1;
    l g = egcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return g;
}

l inv(l a, l mod)
{
    l x, y;
    egcd(a, mod, x, y);
    x %= mod;
    if (x < 0)
        x += mod;
    return x;
}

void solve()
{
    cin >> s;

    l P;
    cin >> P >> M;

    ptr = 0;
    pll res = parse_expr();

    l b = res.ff % M, a = res.ss % M;

    l c = (P - b) % M;
    if (c < 0)
        c += M;

    l g = gcd(a, M);
    a /= g, c /= g;
    
    l mod = M / g;

    l ans = (c * inv(a % mod, mod)) % mod;
    cout << ans;
}

int main()
{
    setIO("");

#ifndef ONLINE_JUDGE
    // setIO("filename");
#endif

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

Compilation message (stderr)

slon.cpp: In function 'void setIO(std::string)':
slon.cpp:53:22: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         (void)freopen((name + ".in").c_str(), "r", stdin);
      |               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
slon.cpp:54:22: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         (void)freopen((name + ".out").c_str(), "w", stdout);
      |               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 120 / 120