Submission #1012950

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1012950	2024-07-03T00:45:42 Z	ds5105119	괄호 문자열 (kriii3_R)	C++17	35 / 113	10000 ms	42240 KB

R

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <unordered_map>


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 2000000;
const double PRIME_CONST = 1.25506; // Rosser (1961)

pii factor_table[N];
pii powers_table[N];
int primes_table[N];


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;
}

void fill_factor(int n) {
    for(int i = 1; i <= n; ++i)
        factor_table[i] = pii(i, 1);
    
    for(int j = 2, j2 = 4; j2 <= n; (j2 += j), (j2 += ++j)) {
        if (factor_table[j].second == 1) {
            int i = j, ij = j2;
            while (ij <= n) {
                factor_table[ij] = pii(j, i);
                i++;
                ij += j;
            }
        }
    }
}

void fill_primes(int n) {
    int idx = 0;
    
    for (int i = 0; i < n; i++) {
        if (factor_table[i].second == 1) {
            primes_table[i] = idx;
            powers_table[idx].first = i;
            idx++;
        }
    }
}

void fill_table(int n) {
    fill_factor(n);
    fill_primes(n);
}

void factor(int n, int d) {
    while (n != 1) {
        powers_table[primes_table[factor_table[n].first]].second += d;
        n = factor_table[n].second;
    }
}

ll get_catalan(int n, int m) {
    ll val = 1;
    double est_power_count = PRIME_CONST * 2 * n / log((double) (2 * n + 1));
    
    for (int i = 0; i < est_power_count; i++) {
        pii power = powers_table[i];
        
        if (power.second != 0) {
            val *= modpow((ll) power.first, power.second, m);
            val %= m;
        }
    }
    
    return val;
}

vector<ll> mod_catalan(vector<ll> queries, ll m) {
    vector<ll> catalans;
    int n = (int)queries.back();
    int idx = 0;
    
    fill_table(4 * n);
    
    while (queries[idx] == 0) {
        catalans.push_back(1);
        idx++;
    }
    
    for (int k = 1; k <= n; k++) {
        factor(4 * k - 2, 1);
        factor(k + 1, -1);
        
        if (queries[idx] == k) {
            ll val = get_catalan(k, (int) m);
            
            while (queries[idx] == k) {
                catalans.push_back(val);
                idx++;
            }
        }
    }
    
    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 n = (int) queries.size();
    
    for(ll i: queries) {
        if (i % 2 == 0) {
            even_val.push_back(i / 2);
        }
    }
    
    if (even_val.size()) {
        catalans = mod_catalan(even_val, m);
    }

    for (int i = 0; i < n; 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> parenthesis_periodicity(int n, ll m) {
    vector<ll> even_range;
    vector<ll> catalans;
    vector<ll> a_l;
    ll a;
    
    for (int i = 0; i <= n; i++)
        even_range.push_back(i);
    
    catalans = mod_catalan(even_range, m);
    
    for (int i = 0; i <= n; i++) {
        a = catalans[i];
        for (ll j = 1; j <= i / 2; j++) {
            a -= (catalans[i - 2 * j] * a_l[j]) % m;
            a %= m;
        }
        a_l.push_back(a);
    }
    
    return a_l;
}

vector<ll> get_c(vector<ll> queries, ll m) {
    vector<ll> a_l;
    vector<ll> c_l = get_b(queries, m);
    int even_max = 0;
    int n = (int) queries.size();
    
    for (int i = 1; i <= n; i++) {
        if (queries[n - i] % 2 == 0) {
            even_max = (int) queries[n - i];
            break;
        }
    }
    
    if (even_max) {
        a_l = parenthesis_periodicity(even_max / 2, m);
        
        for (int i = 0; i < n; i++) {
            if (queries[i] % 2 == 0) {
                c_l[i] -= a_l[(int) queries[i] / 2];
                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 'int main()':
R.cpp:230:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  230 |     scanf("%lld %lld %lld %lld", &p, &q, &m, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
R.cpp:233:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  233 |         scanf("%lld", &l);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1

0 / 38.0

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

Subtask #2

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	8896 KB	Output is correct
2	Correct	109 ms	8888 KB	Output is correct
3	Correct	108 ms	8892 KB	Output is correct
4	Correct	118 ms	9152 KB	Output is correct
5	Correct	117 ms	8892 KB	Output is correct
6	Correct	108 ms	8892 KB	Output is correct

Subtask #3

0 / 40.0

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