| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1000539 |
2024-06-17T16:58:47 Z |
ds5105119 |
괄호 문자열 (kriii3_R) |
C++17 |
|
10000 ms |
32804 KB |
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <unordered_map>
using namespace std;
typedef long long ll;
vector<pair<int, int>> factor_table;
unordered_map<int, int> powers;
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_sieve(int n) {
cout << n << endl;
for (int i = 1; i <= n; i++)
factor_table.push_back(pair<int, int>(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].first = j;
factor_table[ij].second = i;
i++;
ij += j;
}
}
}
}
void factor(int n, int div) {
while (n != 1) {
if (powers.count(factor_table[n].first) == 0) {
powers[factor_table[n].first] = 0;
}
powers[factor_table[n].first] += div;
n = factor_table[n].second;
}
}
vector<ll> mod_catalan(vector<ll> queries, ll m) {
vector<ll> catalans;
int n = (int) queries.back();
ll idx = 0;
ll val = 1;
fill_sieve(4 * n - 2);
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) {
for (auto it : powers) {
if (it.second != 0) {
val *= modpow((ll) it.first, (ll) it.second, m);
val %= m;
}
}
while (queries[idx] == k) {
catalans.push_back(val);
idx++;
}
val = 1;
}
}
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 test() {
vector<ll> result1;
vector<ll> result2;
vector<ll> result3;
vector<ll> result4;
vector<ll> idx;
vector<ll> queries;
ll m = 100000;
// 쿼리 설정
for (int i = 90000; i <= 100000; i++) {
queries.push_back(i);
}
vector<ll> result(queries.size());
for (ll i = 0; i < queries.size(); i++) {
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());
result1 = mod_catalan(queries, m);
result2 = get_a(queries, m);
result3 = get_b(queries, m);
result4 = get_c(queries, m);
cout << "catalans: " << result1.size() << endl;
for (int i = 0; i < queries.size(); i++) {
result[idx[i]] = result1[i];
if (result[idx[i]] < 0) {
result[idx[i]] += m;
}
}
for (ll i : result) {
cout << i << " ";
} cout << endl;
cout << "a" << endl;
for (int i = 0; i < queries.size(); i++) {
result[idx[i]] = result2[i];
if (result[idx[i]] < 0) {
result[idx[i]] += m;
}
}
for (ll i : result) {
cout << i << " ";
} cout << endl;
cout << "b" << endl;
for (int i = 0; i < queries.size(); i++) {
result[idx[i]] = result3[i];
if (result[idx[i]] < 0) {
result[idx[i]] += m;
}
}
for (ll i : result) {
cout << i << " ";
} cout << endl;
cout << "c" << endl;
for (int i = 0; i < queries.size(); i++) {
result[idx[i]] = result4[i];
if (result[idx[i]] < 0) {
result[idx[i]] += m;
}
}
for (ll i : result) {
cout << i << " ";
} cout << endl;
cout << "end" << endl;
return 0;
}
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 test()':
R.cpp:213: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]
213 | for (ll i = 0; i < queries.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
R.cpp:227:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
227 | for (int i = 0; i < queries.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
R.cpp:239:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
239 | for (int i = 0; i < queries.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
R.cpp:251:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
251 | for (int i = 0; i < queries.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
R.cpp:263:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
263 | for (int i = 0; i < queries.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
R.cpp: In function 'int main()':
R.cpp:284:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
284 | scanf("%lld %lld %lld %lld", &p, &q, &m, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
R.cpp:287:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
287 | scanf("%lld", &l);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10075 ms |
22740 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
6852 KB |
Output is correct |
| 2 |
Correct |
144 ms |
6844 KB |
Output is correct |
| 3 |
Correct |
122 ms |
6840 KB |
Output is correct |
| 4 |
Correct |
126 ms |
6844 KB |
Output is correct |
| 5 |
Correct |
125 ms |
6844 KB |
Output is correct |
| 6 |
Correct |
156 ms |
6728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10068 ms |
32804 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
