1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;

const bool DEBUG = !true;

const int P = 0, X = 1, Y = 2;
const int UNION = 1, INTERSECTION = 2, COMPLEMENT = 3;
const int MAX_N = 50'001;
//const int MAX_N = 11;
vector<bitset<MAX_N>> subsets;
vector<array<int, 3>> actions;

void applyAction() {
	array<int, 3> &action = actions.back();
	if (action[P] == UNION) {
		subsets.push_back(subsets[action[X]] | subsets[action[Y]]);
	} else if (action[P] == INTERSECTION) {
		subsets.push_back(subsets[action[X]] & subsets[action[Y]]);
	} else if (action[P] == COMPLEMENT) {
		subsets.push_back(~subsets[action[X]]);
	}
}

void printActions() {
	const int AS = actions.size();
	cout << AS << "\n";
	for (int i = 0; i < AS; i++) {
		if (actions[i][P] == COMPLEMENT) {
			cout << COMPLEMENT << " " << actions[i][X] << "\n";
		} else {
			cout << actions[i][P] << " " << actions[i][X] << " "
					<< actions[i][Y] << "\n";
		}
	}
}
void printSubsets() {
	if (DEBUG) {
		for (auto subset : subsets) {
			cout << subset << endl;
		}
	}
}
int main() {
//	ifstream cin("tests/zb2_0e.in");

	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, s, p;
	cin >> n;
	cin >> s;

	subsets.resize(n + 1);

	for (int i = 0; i < s; i++) {
		cin >> p;
		subsets[0].set(p);
	}

	for (int i = 1; i <= n; i++) {
		for (int p = i; p <= n; p += i) {
			subsets[i].set(p);
		}
	}

	actions.push_back( { COMPLEMENT, 1, 0 });
	applyAction();

	const bitset<MAX_N> &firstSet = subsets[0];
	for (int i = 1; i <= n; i++) {
		const bitset<MAX_N> &lastSet = subsets.back();
		const int S = subsets.size();
		if (firstSet[i] && !lastSet[i]) { // set bit
			actions.push_back( { UNION, i, S - 1 });
			applyAction();
		} else if (!firstSet[i] && lastSet[i]) { // unset bit
			actions.push_back( { COMPLEMENT, i, 0 });
			applyAction();
			actions.push_back( { INTERSECTION, S - 1, S });
			applyAction();
		}

	}

	printSubsets();
	printActions();
//	cout << actions.size() << endl;

	return 0;
}