oj.uz

Submission #1062670

# Submission time Handle Problem Language Result Execution time Memory
1062670 2024-08-17T09:42:34 Z Arapak Digital Circuit (IOI22_circuit) C++17
18 / 100
 3000 ms 6608 KB 
#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;
vector<vi> g;
bool tree_subtask;

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_tree_subtask();
	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) {
	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];
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 4 ms 380 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 2 ms 344 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 4 ms 380 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 2 ms 600 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 2 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 2 ms 600 KB Output is correct
25 Correct 2 ms 600 KB Output is correct
26 Correct 2 ms 600 KB Output is correct
27 Correct 2 ms 600 KB Output is correct
28 Correct 2 ms 600 KB Output is correct
29 Correct 4 ms 344 KB Output is correct
30 Correct 4 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 2 ms 600 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 2 ms 344 KB Output is correct
36 Correct 2 ms 600 KB Output is correct
37 Correct 5 ms 600 KB Output is correct
38 Correct 5 ms 600 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 2 ms 344 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 1 ms 344 KB Output is correct

Subtask #4
0 / 4.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Execution timed out 3016 ms 6608 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 4 ms 380 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 2 ms 600 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 2 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 2 ms 600 KB Output is correct
25 Correct 2 ms 600 KB Output is correct
26 Correct 2 ms 600 KB Output is correct
27 Correct 2 ms 600 KB Output is correct
28 Correct 2 ms 600 KB Output is correct
29 Correct 4 ms 344 KB Output is correct
30 Correct 4 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 2 ms 600 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 2 ms 344 KB Output is correct
36 Correct 2 ms 600 KB Output is correct
37 Correct 5 ms 600 KB Output is correct
38 Correct 5 ms 600 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 2 ms 344 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Execution timed out 3090 ms 976 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 4 ms 380 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 2 ms 600 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 2 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 2 ms 600 KB Output is correct
25 Correct 2 ms 600 KB Output is correct
26 Correct 2 ms 600 KB Output is correct
27 Correct 2 ms 600 KB Output is correct
28 Correct 2 ms 600 KB Output is correct
29 Correct 4 ms 344 KB Output is correct
30 Correct 4 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 2 ms 600 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 2 ms 344 KB Output is correct
36 Correct 2 ms 600 KB Output is correct
37 Correct 5 ms 600 KB Output is correct
38 Correct 5 ms 600 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 2 ms 344 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Execution timed out 3016 ms 6608 KB Time limit exceeded
44 Halted 0 ms 0 KB -