#include "circuit.h"
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#ifdef DEBUG
auto& operator<<(auto& os, pair<auto, auto> &p) {
return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto& os, const auto &v) {
os<<"{";
for(auto it=begin(v);it!=end(v);++it) {
if(it != begin(v)) os<<", ";
os<<(*it);
}
return os<<"}";
}
void dbg_out(auto... x) {
((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif
const ll mod = 1000002022;
int n, m;
vi p, a;
namespace tree_subtask {
bool is;
int base;
vector<ll> tree, inv;
vector<bool> lazy;
void merge(int v) {
int level = (int)floor(log2(v));
int depth = (int)floor(log2(m));
int power = 1<<(depth-level-1);
tree[v] = (tree[v*2] * power % mod + tree[v*2+1] * power % mod + tree[v*2] * tree[v*2+1] % mod) % mod;
inv[v] = (inv[v*2] * power % mod + inv[v*2+1] * power % mod + inv[v*2] * inv[v*2+1] % mod) % mod;
}
void build(int v, int l, int r) {
if(l+1 == r) {
tree[v] = 1; inv[v] = 0;
if(a[l] == 0) swap(tree[v], inv[v]);
return;
}
int mid = (l + r) / 2;
build(v*2, l, mid);
build(v*2+1, mid, r);
merge(v);
}
void init() {
tree.resize(2*m);
inv.resize(2*m);
lazy.assign(2*m, false);
base = m;
build(1, 0, m);
}
void push(int v) {
if(lazy[v]) {
swap(tree[v*2], inv[v*2]);
lazy[v*2] = !lazy[v*2];
swap(tree[v*2+1], inv[v*2+1]);
lazy[v*2+1] = !lazy[v*2+1];
lazy[v] = false;
}
}
void update(int v, int l, int r, int a, int b) {
if(r <= a || b <= l) return;
dbg(v, l, r, a, b);
if(a <= l && r <= b) {
dbg("swap", v);
swap(tree[v], inv[v]);
lazy[v] = !lazy[v];
return;
}
int mid = (l + r) / 2;
push(v);
update(v*2, l, mid, a, b);
update(v*2+1, mid, r, a, b);
merge(v);
}
int count_ways(int L, int R) {
dbg(L, R);
dbg(tree);
dbg(inv );
update(1, 0, m, L-n, R-n+1);
dbg(tree);
dbg(inv );
dbg(lazy);
return tree[1];
}
}
vector<vi> g;
bool is_tree_subtask() {
// int b = (int)bit_ceil(uint(m));
int b = 1;
while(b < m) b *= 2;
if(b != m || m != n+1) return false;
rep(i,1,n+m)
if(p[i] != (i-1) / 2) return false;
return true;
}
void init(int N, int M, vi P, vi A) {
n = N; m = M; p = P; a = A;
tree_subtask::is = is_tree_subtask();
if(tree_subtask::is) {
dbg("TREE");
tree_subtask::init();
return;
}
g.resize(n);
rep(i,1,n+m)
g[p[i]].push_back(i);
}
vector<ll> multiply(const vector<ll> &a, const vector<ll> &b) {
vector<ll> res(sz(a) + sz(b) - 1);
rep(i,0,sz(a)) rep(j,0,sz(b))
res[i+j] = (res[i+j] + a[i] * b[j]) % mod;
dbg(a, b, res);
return res;
}
int count_ways(int L, int R) {
if(tree_subtask::is) {
return tree_subtask::count_ways(L, R);
}
dbg(L, R);
rep(i,L,R+1)
a[i-n] = !a[i-n];
dbg(a);
vector<vector<ll>> dp(n+m);
rep(i,0,m) dp[n+i] = a[i] ? vector<ll>({0, 1}) : vector<ll>({1, 0});
for(int i=n-1;i>=0;i--) {
dbg(i);
vector<vector<ll>> v = {{1, 0}};
for(auto e : g[i]) {
dbg(e);
vector<ll> vec = dp[e];
while(!v.empty() && sz(v.back()) == sz(vec)) {
vec = multiply(vec, v.back());
v.pop_back();
}
v.push_back(vec);
dbg(v);
}
while(sz(v) > 1) {
auto a = v.back(); v.pop_back();
auto b = v.back(); v.pop_back();
v.push_back(multiply(a, b));
}
const vector<ll> &val = v[0];
dbg(val);
dp[i] = {0, 0};
ll all = 0;
rep(j,0,sz(g[i]) + 1)
all = (all + val[j]) % mod;
ll sum = val[0];
rep(j,1,sz(g[i]) + 1) {
dp[i][0] = (dp[i][0] + sum) % mod;
dp[i][1] = (dp[i][1] + all + mod - sum) % mod;
sum = (sum + val[j]) % mod;
}
}
return dp[0][1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
2nd lines differ - on the 1st token, expected: '2', found: '3' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
2nd lines differ - on the 1st token, expected: '2', found: '3' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
2nd lines differ - on the 1st token, expected: '2', found: '3' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
489 ms |
2648 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '547151666' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
489 ms |
2648 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '547151666' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
2nd lines differ - on the 1st token, expected: '2', found: '3' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
2nd lines differ - on the 1st token, expected: '2', found: '3' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
2nd lines differ - on the 1st token, expected: '2', found: '3' |
| 2 |
Halted |
0 ms |
0 KB |
- |
