Submission #1087903

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1087903	2024-09-13T11:31:21 Z	nguyen31hoang08minh2003	Slon (COCI15_slon)	C++17	120 / 120	3 ms	1116 KB

slon

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#include <numeric>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <strings.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

constexpr int MAX_LENGTH = 100'005;

signed length, positions[MAX_LENGTH];
stack<int> s;
string A;
int P, M;

int getAddition(int x, const int y) {
    if ((x += y) >= M)
        x -= M;
    return x;
}

int getSubtraction(int x, const int y) {
    if ((x -= y) < 0)
        x += M;
    return x;
}

int getMultiplication(const ll x, const ll y) {
    return x * y % M;
}

pair<int, int> getMultiplication(const pair<int, int> &A, const pair<int, int> &B) {
    return make_pair(getAddition(getMultiplication(A.first, B.second), getMultiplication(A.second, B.first)), getMultiplication(A.second, B.second));
}

pair<int, int> getAddition(const pair<int, int> &A, const pair<int, int> &B) {
    return make_pair(getAddition(A.first, B.first), getAddition(A.second, B.second));
}

pair<int, int> getSubtraction(const pair<int, int> &A, const pair<int, int> &B) {
    return make_pair(getSubtraction(A.first, B.first), getSubtraction(A.second, B.second));
}

pair<int, int> simplify(const int l, const int r) {
    vector<pair<int, int> > values;
    vector<char> operations;

    for (int i = l; i <= r;) {
        if (isdigit(A[i])) {
            int value = 0;

            for (; i <= r && isdigit(A[i]); ++i)
                value = getAddition(getMultiplication(value, 10), A[i] - '0');

            values.emplace_back(0, value);
            continue;
        }
        if (A[i] == '(') {
            values.push_back(simplify(i + 1, positions[i] - 1));
            i = positions[i] + 1;
            continue;
        }
        if (A[i] == 'x') {
            values.emplace_back(1, 0);
            ++i;
            continue;
        }
        operations.push_back(A[i]);
        ++i;
    }

    const int valueCount = values.size();
    vector<pair<int, int> > expressions;
    pair<int, int> result;
    vector<char> changes;

    expressions.push_back(values.front());

    for (int i = 1; i < valueCount; ++i) {
        if (operations[i - 1] != '*') {
            expressions.push_back(values[i]);
            changes.push_back(operations[i - 1]);
            continue;
        }
        expressions.back() = getMultiplication(expressions.back(), values[i]);
    }

    const int expressionCount = expressions.size();

    result = expressions.front();

    for (int i = 1; i < expressionCount; ++i)
        if (changes[i - 1] == '+')
            result = getAddition(result, expressions[i]);
        else
            result = getSubtraction(result, expressions[i]);

    return result;
}

signed main() {

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> A >> P >> M;

    length = A.size();

    for (int i = 0; i < length; ++i) {
        if (A[i] != '(' && A[i] != ')')
            continue;
        if (A[i] == '(') {
            s.push(i);
            continue;
        }
        if (A[i] == ')') {
            const int &j = s.top();
            positions[j] = i;
            positions[i] = j;
            s.pop();
            continue;
        }
    }

    const auto [a, b] = simplify(0, length - 1);

    for (int x = 0; x < M; ++x)
        if (getAddition(getMultiplication(a, x), b) == P) {
            cout << x << '\n';
            return 0;
        }

    return 0;
}

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	348 KB	Output is correct
2	Correct	3 ms	1116 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	652 KB	Output is correct
9	Correct	1 ms	656 KB	Output is correct
10	Correct	2 ms	860 KB	Output is correct