Submission #696047

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
696047	2023-02-05T09:14:48 Z	Nhoksocqt1	Slon (COCI15_slon)	C++17	96 / 120	5 ms	468 KB

slon

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

int readInt() {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while(true) {
		if(ch == '-') break;
		if(ch >= '0' && ch <= '9') break;
		ch = getchar();
	}

	if(ch == '-') minus = true; else result = ch - '0';
	while(true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result * 10 + (ch - '0');
	}

	if(minus)
		return -result;
	else
		return result;
}

string str;
int strLen, P, M;

ii add(ii a, ii b, char c) {
    return {(a.fi + (c == '-' ? -1 : 1) * b.fi + M) % M, (a.se + (c == '-' ? -1 : 1) * b.se + M) % M};
}

void whileIsMul(stack<ii> &st, stack<char> &ope) {
    while(ope.size() && ope.top() == '*') {
        ii x = st.top(); st.pop();
        ii y = st.top(); st.pop();
        x.se = 1LL * x.se * y.fi % M + 1LL * y.se * x.fi % M;
        x.fi = 1LL * x.fi * y.fi % M;
        st.push(x);
        ope.pop();
    }
}

void process() {
    cin >> str >> P >> M;
    strLen = str.size();
    str = '^' + str;

    stack<ii> st;
    stack<char> ope;
    for (int i = 1; i <= strLen; ++i) {
        if(str[i] == '(') {
            ope.push(str[i]);
            continue;
        }

        if(str[i] == ')') {
            while(ope.top() != '(') {
                ii x = st.top(); st.pop();
                ii y = st.top(); st.pop();
                st.push(add(y, x, ope.top()));
                ope.pop();
            }

            ope.pop();
            whileIsMul(st, ope);
            continue;
        }

        if(str[i] >= '0' && str[i] <= '9' || str[i] == 'x') {
            if(str[i] >= '0' && str[i] <= '9') {
                int num(0);
                while(i <= strLen && str[i] >= '0' && str[i] <= '9') {
                    num = num * 10 + str[i] - '0';
                    ++i;
                }

                --i;
                st.push({num % M, 0});
            } else {
                st.push({0, 1});
            }

            whileIsMul(st, ope);
            continue;
        }

        ope.push(str[i]);
    }

    while(ope.size()) {
        ii x = st.top(); st.pop();
        ii y = st.top(); st.pop();
        st.push(add(y, x, ope.top()));
        ope.pop();
    }

    ii x = st.top();
    for (int i = 0; i < M; ++i) {
        if((1LL * i * x.se + x.fi) % M == P) {
            cout << i << '\n';
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("slon.inp", "r", stdin);
//    freopen("slon.out", "w", stdout);

    process();
    return 0;
}

Compilation message

slon.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
slon.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
slon.cpp: In function 'void process()':
slon.cpp:91:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   91 |         if(str[i] >= '0' && str[i] <= '9' || str[i] == 'x') {

Subtask #1

96.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	212 KB	Output is correct
2	Incorrect	4 ms	468 KB	Output isn't correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	2 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	3 ms	212 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Incorrect	2 ms	340 KB	Output isn't correct
10	Correct	1 ms	468 KB	Output is correct