Submission #1087903

#TimeUsernameProblemLanguageResultExecution timeMemory
1087903nguyen31hoang08minh2003Slon (COCI15_slon)C++17
120 / 120
3 ms1116 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...