Submission #255087

# Submission time Handle Problem Language Result Execution time Memory
255087 2020-07-31T09:06:01 Z Vimmer Slon (COCI15_slon) C++14
0 / 120
1000 ms 764 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;

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 += otr * pt.F.F;

                kf += otr * pt.F.S;

                i--;

                continue;
            }
            else
             {
                ll cur = max(1ll, pt.F.F), kft = 0, from = 1;

                if (pt.F.S != 0) {from = max(1ll, pt.F.F); kft = pt.F.S;}

                i++;

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

                        if (pt.F.F != 0) cur *= pt.F.F;

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

                        i = pt.S;

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

                        kft *= cur; kft /= from;

                        kf += kft * otr;

                        if (kft == 0) val += cur * otr;

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

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

                        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';}

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

                    if (num == -1) kft = 1; else cur *= num;

                    i += j + 1;

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

                    kft *= cur; kft /= from;

                    kf += kft * otr;

                    if (kft == 0) val += cur * otr;

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

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

                    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';}

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

        i += j + 1;

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

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

        if (a[i] == ')')
        {
            if (num == -1) kf += otr;
              else val += otr * num;

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

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

            if (num != -1) cur = num; else kft = 1;
            i++;

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

                    if (pt.F.F != 0) cur *= pt.F.F;

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

                    i = pt.S;

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

                    kft *= cur; kft /= from;

                    kf += kft * otr;

                    if (kft == 0) val += cur * otr;

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

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

                    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';}

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

                if (num == -1) kft = 1; else cur *= num;

                i += j + 1;

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

                kft *= cur; kft /= from;

                kf += kft * otr;

                if (kft == 0) val += cur * otr;

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

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

                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;


    a = '(' + a;

    a = a + ')';

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

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

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

    ll p, m;

    cin >> p >> m;
    ll x = 0;

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

        x++;
    }
}

Compilation message

slon.cpp: In function 'std::pair<std::pair<long long int, long long int>, int> calc(int)':
slon.cpp:223:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Incorrect 3 ms 764 KB Output isn't correct
3 Execution timed out 1094 ms 256 KB Time limit exceeded
4 Incorrect 15 ms 384 KB Output isn't correct
5 Execution timed out 1092 ms 384 KB Time limit exceeded
6 Incorrect 5 ms 384 KB Output isn't correct
7 Incorrect 1 ms 384 KB Output isn't correct
8 Incorrect 22 ms 512 KB Output isn't correct
9 Incorrect 2 ms 512 KB Output isn't correct
10 Incorrect 2 ms 640 KB Output isn't correct