Submission #544317

#	Time	Username	Problem	Language	Result	Execution time	Memory
544317		Olympia	Slon (COCI15_slon)	C++17	0 / 120	7 ms	588 KiB

slon

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <bitset>
#include <stack>
#include <cstdlib>
#include <queue>
#include <stdint.h>
#include <vector>
#include <cassert>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <limits.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;

int MOD;

struct Polynomial {
    int64_t x;
    int64_t a;

    Polynomial operator+(Polynomial p) const {
        return {(p.x + x + 2 * MOD) % MOD, (p.a + a + 2 * MOD) % MOD};
    }

    Polynomial operator*(Polynomial p) const {
        return {(p.x * a + p.a * x) % MOD, (p.a * a) % MOD};
    }

    Polynomial operator-(Polynomial p) const {
        return {(2 * MOD-p.x) % MOD, (2 * MOD-p.a) % MOD};
    }
};

int ordering(char c) {
    if (c == '+' || c == '-') return 1;
    if (c == '*') return 2;
    return 0;
}

Polynomial applyOp(Polynomial p1, Polynomial p2, char c) {
    if (c == '+') return p1 + p2;
    if (c == '*') return p1 * p2;
    if (c == '-') return p1 - p2;
    return {-1, -1};
}

int main() {
    //freopen("balancing.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    int modulo; cin >> modulo;
    cin >> MOD;
    stack<char> ops;
    stack<Polynomial> values;
    int i;

    for (i = 0; i < s.length(); i++) {
        if (s[i] == ' ')
            continue;
        else if (s[i] == '(') {
            ops.push(s[i]);
        } else if (isdigit(s[i])) {
            int val = 0;
            while (i < s.length() && isdigit(s[i])) {
                val = (val * 10) + (s[i] - '0');
                i++;
            }
            values.push({0, val});
            i--;
        } else if (s[i] == ')') {
            while (!ops.empty() && ops.top() != '(') {
                Polynomial val2 = values.top();
                values.pop();
                Polynomial val1 = values.top();
                values.pop();
                char op = ops.top();
                ops.pop();
                values.push(applyOp(val1, val2, op));
            }
            if (!ops.empty()) {
                ops.pop();
            }
        } else if (s[i] == 'x') {
            values.push({1, 0});
        } else {
            while (!ops.empty() && ordering(ops.top()) >= ordering(s[i])) {
                Polynomial val2 = values.top();
                values.pop();
                Polynomial val1 = values.top();
                values.pop();
                char op = ops.top();
                ops.pop();
                values.push(applyOp(val1, val2, op));
            }
            ops.push(s[i]);
        }
    }
    while (!ops.empty()) {
        Polynomial val2 = values.top();
        values.pop();
        Polynomial val1 = values.top();
        values.pop();
        char op = ops.top();
        ops.pop();
        values.push(applyOp(val1, val2, op));
    }
    for (int x = 0; x < MOD; x++) {
        if ((values.top().a + values.top().x * x) % MOD == modulo) {
            cout << x;
            exit(0);
        }
    }

}

Compilation message (stderr)

slon.cpp:25: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   25 | #pragma GCC optimization ("O3")
      | 
slon.cpp:26: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   26 | #pragma GCC optimization ("unroll-loops")
      | 
slon.cpp: In function 'int main()':
slon.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (i = 0; i < s.length(); i++) {
      |                 ~~^~~~~~~~~~~~
slon.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             while (i < s.length() && isdigit(s[i])) {
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 0 / 120