#include <bitset> #include <iostream> #include <vector> using namespace std; #define LIMIT 50000 typedef bitset<LIMIT> bset; int n, s, m; class Node { public: int o, x, y; }; bset pattern; bset bs; vector<Node> nodes; vector<bset> sets; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> s; for(int i = 1; i <= n; i++) { bset b; for(int j = 1; j <= LIMIT; j++) { if(j % i == 0) { b[j-1] = 1; } } sets.push_back(b); } for (int i = 0; i < s; i++) { int b; cin >> b; pattern[b - 1] = 1; } int lastIndex = -1; for (int i = 0; i < n; i++) { int bit = bs[i]; int pbit = pattern[i]; if (bit != pbit) { if (pbit) { bs |= sets[i]; if (lastIndex == -1) { lastIndex = i; } else { Node node = Node(1, lastIndex, i); nodes.push_back(node); lastIndex = m + n; m++; } } else { bs &= (~sets[i]); Node node = Node(3, i); nodes.push_back(node); m++; Node node2 = Node(2, lastIndex, n + m - 1); nodes.push_back(node2); lastIndex = m + n; m++; } } } if(lastIndex != n + m - 1) { cout << 1 << endl; cout << 1 << " " << lastIndex+1 << " " << lastIndex+1 << endl; return 0; } cout << m << endl; for(int i = 0; i < m; i++) { Node node = nodes[i]; cout << node.o << " " << node.x+1; if(node.o < 3) { cout << " " << node.y+1 << endl; } else { cout << endl; } } return 0; }
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 92 | #include <bitset> #include <iostream> #include <vector> using namespace std; #define LIMIT 50000 typedef bitset<LIMIT> bset; int n, s, m; class Node { public: int o, x, y; }; bset pattern; bset bs; vector<Node> nodes; vector<bset> sets; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> s; for(int i = 1; i <= n; i++) { bset b; for(int j = 1; j <= LIMIT; j++) { if(j % i == 0) { b[j-1] = 1; } } sets.push_back(b); } for (int i = 0; i < s; i++) { int b; cin >> b; pattern[b - 1] = 1; } int lastIndex = -1; for (int i = 0; i < n; i++) { int bit = bs[i]; int pbit = pattern[i]; if (bit != pbit) { if (pbit) { bs |= sets[i]; if (lastIndex == -1) { lastIndex = i; } else { Node node = Node(1, lastIndex, i); nodes.push_back(node); lastIndex = m + n; m++; } } else { bs &= (~sets[i]); Node node = Node(3, i); nodes.push_back(node); m++; Node node2 = Node(2, lastIndex, n + m - 1); nodes.push_back(node2); lastIndex = m + n; m++; } } } if(lastIndex != n + m - 1) { cout << 1 << endl; cout << 1 << " " << lastIndex+1 << " " << lastIndex+1 << endl; return 0; } cout << m << endl; for(int i = 0; i < m; i++) { Node node = nodes[i]; cout << node.o << " " << node.x+1; if(node.o < 3) { cout << " " << node.y+1 << endl; } else { cout << endl; } } return 0; } |