Submission #255745

#	Time	Username	Problem	Language	Result	Execution time	Memory
255745		Vimmer	Slon (COCI15_slon)	C++14	12 / 120	1095 ms	640 KiB

slon

#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;}
ll mult(ll x, ll y) {return (x * y) % m;}

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

pair <pair <ll, ll>, int>  calc(int v)
{

    ll kf = 0, val = 0, otr = 1;

    for (int i = v + 1; i < sz(a); i++)
    {
        if (a[i] == ')') return {{val, kf}, i + 1};

        if (a[i] == '(')
        {
            pair <pair <ll, ll>, int> 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
             {

                ll cur = max(1ll, pt.F.F), kft = 0, from = 1, dob = 0;

                if (pt.F.S != 0) kft = pt.F.S;
                  else from = cur;

                i++;

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

                        if (pt.F.S == 0) from = mult(from, pt.F.F);

                        if (pt.F.S != 0) kft = pt.F.S;

                        if (pt.F.F != 0) {if (kft == 0 || pt.F.S != 0) dob = 1; cur = mult(cur, pt.F.F);}

                        i = pt.S;

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

                        kft = mult(kft, from);

                        kf = sm(kf, mult(kft, otr));

                        if (kft == 0) val = sm(val, mult(cur, otr));
                        else
                        val = sm(val, mult(dob, mult(cur, otr)));

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

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

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

                        break;
                    }

                    ll num = 0, j = 0;

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

                    for (int 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;

                    if (num == -1) {kft = 1;}else {from = mult(from, num); cur = mult(cur, num);}

                    i += j + 1;

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

                    kft = mult(from, kft);

                    kf = sm(kf, mult(kft, otr));

                    if (kft == 0) val = sm(val, mult(cur, otr));
                    else
                    val = sm(val, mult(dob, mult(cur, otr)));

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

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

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

                    break;
                }
            }

            continue;
        }

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

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

        int j = 0;

        ll num = 0;

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

        for (int 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;

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

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

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

            return {{val, kf}, i + 1};
        }

        {
            ll cur = 1, kft = 0, from = 1, dob = 0;

            if (num != -1)
                {
                    from = mult(from, num); cur = num;} else kft = 1;

            i++;

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

                    if (pt.F.S == 0) from = mult(from, pt.F.F);

                    if (pt.F.S != 0) kft = pt.F.S;

                    if (pt.F.F != 0) {if (kft == 0 || pt.F.S != 0) dob = 1; cur = mult(cur, pt.F.F);}

                    i = pt.S;

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

                    kft = mult(kft, from);

                    kf = sm(kf, mult(kft, otr));

                    if (kft == 0) val = sm(val, mult(cur, otr));
                    else
                    val = sm(val, mult(dob, mult(cur, otr)));

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

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

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

                    break;
                }

                ll num = 0, j = 0;

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

                for (int 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;

                if (num == -1)
                {
                    kft = 1;

                } else {cur = mult(cur, num); from = mult(from, num);}

                i += j + 1;

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

                kft = mult(kft, from);

                kf = sm(kf, mult(kft, otr));

                if (kft == 0) val = sm(val, mult(cur, otr));
                else
                val = sm(val, mult(dob, mult(cur, otr)));

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

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

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

                break;
            }
        }
    }
}
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>, int> pt = calc(0);

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

    p -= val;

    p = sm(p, m);

    ll x = 0;

    while (1)
    {
        if ((x * kf) % m == p) {cout << x << endl; exit(0);}

        x++;
    }
}

Compilation message (stderr)

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

• Subtask 1: 12 / 120