oj.uz

Submission #995105

# Submission time Handle Problem Language Result Execution time Memory
995105 2024-06-08T12:57:33 Z ds5105119 괄호 문자열 (kriii3_R) C++17
35 / 113
 10000 ms 14668 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;

ll modpow(ll b, ll e, ll m) {
  b %= m;
  ll ret = 1;
  while (e > 0) {
    if (e & 1)
        ret = (ret * b) % m;
    b = (b * b) % m;
    e >>= 1;
  }
  return ret;
}

vector<ll> mod_catalan(vector<ll> queries, ll m) {
    vector<ll> catalans = {1};
    vector<ll> results;
    ll val = 0;
    ll idx = 0;
    
    if (queries.empty()) {
        return queries;
    }

    for (ll n = 0; n <= queries.back(); n++) {
        while (n == queries[idx]) {
            results.push_back(catalans.back());
            idx++;
        }
        
        for (int i = 0; i <= n; i++) {
            val += catalans[i] * catalans[n - i] % m;
        } 
        
        catalans.push_back(val % m);
        val = 0;
    }

    return catalans;
}

vector<ll> get_a(vector<ll> queries, ll m) {
    vector<ll> even_val;
    vector<ll> catalans;
    ll val = 0;
    ll idx = 0;
    int len = (int)queries.size();
    
    for(ll i: queries) {
        if (i % 2 == 0) {
            even_val.push_back(i / 2ll);
        }
    }
    
    catalans = mod_catalan(even_val, m);

    for (int i = 0; i < len; i++) {
        val = modpow(2ll, queries[i], m);
        if (queries[i] % 2 == 0) {
            val -= catalans[idx];
            val %= m;
            idx++;
        }
        queries[i] = val;
    }
    
    return queries;
}

vector<ll> get_b(vector<ll> queries, ll m) {
    vector<ll> b_l;
    deque<ll> b_q = {};
    ll b_i = 1;
    ll idx = 0;
    ll mid = queries.back() / 2ll + 1ll;
    
    for (int i = 1; i <= queries.back(); i++) {
        if (i % 2) {
            b_i = (2ll * b_i) % m;
        } else {
            b_i = (2ll * b_i - b_q.front()) % m;
            b_q.pop_front();
        }

        if (i < mid) {
            b_q.push_back(b_i);
        }

        while (i == queries[idx]) {
            b_l.push_back(b_i);
            idx++;
        }
    }

    return b_l;
}

vector<ll> get_c(vector<ll> queries, ll m) {
    vector<ll> even_range;
    vector<ll> catalans;
    vector<ll> a_l;
    vector<ll> c_l = get_b(queries, m);
    ll a;
    ll even_max = 0;
    
    for (ll i : queries) {
        if (i % 2 == 0) {
            even_max = i;
        }
    }
    
    for (ll i = 0; i <= even_max / 2ll; i++)
        even_range.push_back(i);
    
    catalans = mod_catalan(even_range, m);
    
    for (ll i = 0; i <= even_max / 2ll; i++) {
        a = catalans[i];
        for (ll j = 1; j <= i / 2ll; j++) {
            a -= (catalans[i - 2ll * j] * a_l[j]) % m;
            a %= m;
        }
        a_l.push_back(a);
    }
    
    for (ll i = 0; i < c_l.size(); i++) {
        if (queries[i] % 2 == 0) {
            c_l[i] -= a_l[queries[i] / 2ll];
            c_l[i] %= m;
        }
    }
    
    return c_l;
}

int main() {
    ll p, q, m, Q, l;
    vector<ll> queries;
    vector<ll> result;
    vector<ll> idx;
    scanf("%lld %lld %lld %lld", &p, &q, &m, &Q);
    
    for (int i = 0; i < Q; i++) {
        scanf("%lld", &l);
        queries.push_back(l);
        idx.push_back(i);
    }
    
    sort(idx.begin(), idx.end(), [&queries](size_t i, size_t j)
         { return queries[i] < queries[j]; });
    sort(queries.begin(), queries.end());
    
    if (p == 1 && q == 0) {
        result = get_a(queries, m);
    } else if (p == 0 && q == 1) {
        result = get_b(queries, m);
    } else if (p == 1 && q == 1) {
        result = get_c(queries, m);
    } else {
        return 0;
    }
    
    for (int i = 0; i < Q; i++) {
        queries[idx[i]] = result[i];
        if (queries[idx[i]] < 0) {
            queries[idx[i]] += m;
        }
    }
    
    for (ll i : queries) {
        cout << i << endl;
    }

    return 0;
}

Compilation message

R.cpp: In function 'std::vector<long long int> get_c(std::vector<long long int>, ll)':
R.cpp:133:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (ll i = 0; i < c_l.size(); i++) {
      |                    ~~^~~~~~~~~~~~
R.cpp: In function 'int main()':
R.cpp:148:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |     scanf("%lld %lld %lld %lld", &p, &q, &m, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
R.cpp:151:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         scanf("%lld", &l);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 38.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10060 ms 5032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 6080 KB Output is correct
2 Correct 124 ms 6080 KB Output is correct
3 Correct 124 ms 6072 KB Output is correct
4 Correct 124 ms 6076 KB Output is correct
5 Correct 131 ms 6080 KB Output is correct
6 Correct 125 ms 5972 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10025 ms 14668 KB Time limit exceeded
2 Halted 0 ms 0 KB -