Submission #1038820

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1038820	2024-07-30T08:00:24 Z	vjudge1	Slon (COCI15_slon)	C++17	120 / 120	109 ms	1920 KB

slon

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

const int N = 1e5 + 10;
pair<int, int> a[N];
string s;
int p, m, go[N];

bool cmp(pair<int, int> a, pair<int, int> b){
    return ((a.second - a.first) <= (b.second - b.first));
}

int main(){
    string s;
    cin >> s;
    s = '(' + s + ')';
    cin >> p >> m;

    vector<int> li;
    vector<pair<int, int>> vec;
    for (int i = 0; i < s.size(); i ++){
        go[i] = i + 1;
        if (s[i] == '(') li.push_back(i);
        else if (s[i] == ')'){
            vec.push_back({li.back(), i});
            go[li.back()] = i + 1;
            li.pop_back();
        }
        else if ('0' <= s[i] and s[i] <= '9'){
            int j = i;
            int x = 0;
            while ('0' <= s[j] and s[j] <= '9'){
                x = x * 10 + s[j] - '0';
                x %= m;
                j++;
            }
            go[i] = j;
            a[i] = {0, x};
            i = j - 1;
        }
        else if (s[i] == 'x')
            a[i] = {1, 0};
    }

    sort(vec.begin(), vec.end(), cmp);

    for (int k = 0; k < vec.size(); k ++){
        int l = vec[k].first;
        int r = vec[k].second;

        // cout << endl << l << " -- " << r << endl;
        
        pair<long long, long long> cur = {0, 0};
        vector<pair<long long, long long>> process;
        string signs;

        for (int i = l + 1; i < r;){
            if (s[i] == '+' or s[i] == '*' or s[i] == '-'){
                signs += s[i];
                i = go[i];
            }
            else if (s[i] == ')'){
                i = go[i];
            }
            else{
                process.push_back(a[i]);
                i = go[i];
            }
        }

        // cout << signs << endl;
        // for (auto [x, y] : process)
        //     cout << x << " " << y << endl;

        for (int i = 0; i < signs.size(); i ++){
            if (signs[i] == '*'){
                process[i + 1].first = process[i + 1].first * process[i].second + process[i].first * process[i + 1].second;
                process[i + 1].second = process[i].second * process[i + 1].second;

                process[i + 1].first %= m;
                process[i + 1].second %= m;

                process[i].first = 1e9;
                process[i].second = 1e9;
            }
        }
        // for (auto [x, y] : process)
        //     cout << x << " " << y << endl;

        for (int i = 0; i < signs.size(); i ++){
            if (signs[i] == '*') continue;

            while (process[i].first == 1e9) i++;

            int j = i + 1;
            while (process[j].first == 1e9) j++;

            if (signs[i] == '+'){
                process[j].first += process[i].first;
                process[j].second += process[i].second;
            }
            else{
                process[j].first = process[i].first - process[j].first;
                process[j].second = process[i].second - process[j].second;            
            }

            process[j].first %= m;
            process[j].second %= m;
        }

        a[l] = process.back();
        // cout << "val = " << a[l].first << " " << a[l].second << endl;
    }

    int c1 = a[0].first;
    int c0 = a[0].second;

    c1 += m;
    c0 += m;
    
    c1 %= m;
    c0 %= m;

    for (int x = 0; x < m; x ++){
        long long val = ((1ll * c1 * x) % m) + c0;
        val %= m;
        if (val == p){
            cout << x << endl;
            return 0;
        }
    }
}

Compilation message

slon.cpp: In function 'int main()':
slon.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < s.size(); i ++){
      |                     ~~^~~~~~~~~~
slon.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int k = 0; k < vec.size(); k ++){
      |                     ~~^~~~~~~~~~~~
slon.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int i = 0; i < signs.size(); i ++){
      |                         ~~^~~~~~~~~~~~~~
slon.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int i = 0; i < signs.size(); i ++){
      |                         ~~^~~~~~~~~~~~~~
slon.cpp:53:36: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
   53 |         pair<long long, long long> cur = {0, 0};
      |                                    ^~~

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	348 KB	Output is correct
2	Correct	109 ms	1920 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	2 ms	348 KB	Output is correct
7	Correct	2 ms	604 KB	Output is correct
8	Correct	9 ms	960 KB	Output is correct
9	Correct	15 ms	1368 KB	Output is correct
10	Correct	70 ms	1628 KB	Output is correct