#include <bitset> #include <iostream> #include <vector> constexpr int MAX_N = 50000; constexpr int MAX_M = 2*MAX_N; enum class OperationType { Sum = 1, And = 2, Neg = 3 }; class Operation { public: OperationType type{}; int x{}; int y{}; Operation(OperationType type, int x, int y): type(type), x(x), y(y) { } void print() const { if(type == OperationType::Neg) { std::cout << (int)type << " " << x << "\n"; return; } std::cout << (int)type << " " << x << " " << y << "\n"; } }; class InputParams { public: int n{}; int s{}; }; InputParams loadData() { InputParams params; std::cin >> params.n; std::cin >> params.s; return params; } void addNegOperation(std::bitset<MAX_N>& outSet, std::vector<Operation>& operations, int x) { operations.emplace_back(OperationType::Neg, x, 0); outSet.flip(); } void addAndOperation(std::bitset<MAX_N>& outSet, const std::vector<std::bitset<MAX_N>> &sets, std::vector<Operation>& operations, int x, int y) { operations.emplace_back(OperationType::And, x, y); outSet = outSet & sets[y - 1]; } void addOrOperation(std::bitset<MAX_N>& outSet, const std::vector<std::bitset<MAX_N>> &sets, std::vector<Operation>& operations, int x, int y) { operations.emplace_back(OperationType::Sum, x, y); outSet = outSet | sets[y - 1]; } void fillInitialSets(std::vector<std::bitset<MAX_N>> &sets, const InputParams ¶ms) { sets.emplace_back(); sets[0].set(); for (int n = 2; n <= params.n; n++) { sets.emplace_back(); std::bitset<MAX_N> ¤tSet = sets[n - 1]; for (int i = n; i <= MAX_N; i += n) { currentSet.set(i - 1); } } } void loadTargetSet(std::bitset<MAX_N>& targetSet, const InputParams ¶ms) { int x; for(int i = 0; i < params.s; i++) { std::cin >> x; targetSet.set(x - 1); } } void fillCurrentSet(std::bitset<MAX_N>& currentSet, std::vector<std::bitset<MAX_N>> &sets, const InputParams ¶ms) { currentSet = sets[params.n - 1]; } void fillOperations(std::vector<Operation>& operations, std::bitset<MAX_N>& currentSet, std::bitset<MAX_N>& targetSet, std::vector<std::bitset<MAX_N>> &sets, const InputParams ¶ms) { int currentX = params.n; bool isFlipped = false; for(int i = 0; i < params.n; i++) { if(currentSet[i] == targetSet[i]) { continue; } if(currentSet.test(i)) { // flip and do sum addNegOperation(currentSet, operations, currentX); currentX++; addOrOperation(currentSet, sets, operations, currentX, i + 1); currentX++; targetSet.flip(); isFlipped = !isFlipped; } else { // do sum addOrOperation(currentSet, sets, operations, currentX, i + 1); currentX++; } } if(isFlipped) { addNegOperation(currentSet, operations, currentX); } } void printOperations(const std::vector<Operation>& operations) { std::cout << operations.size() << "\n"; for(int i = 0; i < operations.size(); i++) { operations[i].print(); } } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::vector<std::bitset<MAX_N>> sets; sets.reserve(MAX_N); std::bitset<MAX_N> targetSet; std::bitset<MAX_N> currentSet; std::vector<Operation> operations; operations.reserve(MAX_M); InputParams params = loadData(); fillInitialSets(sets, params); loadTargetSet(targetSet, params); fillCurrentSet(currentSet, sets, params); fillOperations(operations, currentSet, targetSet, sets, params); printOperations(operations); 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 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 | #include <bitset> #include <iostream> #include <vector> constexpr int MAX_N = 50000; constexpr int MAX_M = 2*MAX_N; enum class OperationType { Sum = 1, And = 2, Neg = 3 }; class Operation { public: OperationType type{}; int x{}; int y{}; Operation(OperationType type, int x, int y): type(type), x(x), y(y) { } void print() const { if(type == OperationType::Neg) { std::cout << (int)type << " " << x << "\n"; return; } std::cout << (int)type << " " << x << " " << y << "\n"; } }; class InputParams { public: int n{}; int s{}; }; InputParams loadData() { InputParams params; std::cin >> params.n; std::cin >> params.s; return params; } void addNegOperation(std::bitset<MAX_N>& outSet, std::vector<Operation>& operations, int x) { operations.emplace_back(OperationType::Neg, x, 0); outSet.flip(); } void addAndOperation(std::bitset<MAX_N>& outSet, const std::vector<std::bitset<MAX_N>> &sets, std::vector<Operation>& operations, int x, int y) { operations.emplace_back(OperationType::And, x, y); outSet = outSet & sets[y - 1]; } void addOrOperation(std::bitset<MAX_N>& outSet, const std::vector<std::bitset<MAX_N>> &sets, std::vector<Operation>& operations, int x, int y) { operations.emplace_back(OperationType::Sum, x, y); outSet = outSet | sets[y - 1]; } void fillInitialSets(std::vector<std::bitset<MAX_N>> &sets, const InputParams ¶ms) { sets.emplace_back(); sets[0].set(); for (int n = 2; n <= params.n; n++) { sets.emplace_back(); std::bitset<MAX_N> ¤tSet = sets[n - 1]; for (int i = n; i <= MAX_N; i += n) { currentSet.set(i - 1); } } } void loadTargetSet(std::bitset<MAX_N>& targetSet, const InputParams ¶ms) { int x; for(int i = 0; i < params.s; i++) { std::cin >> x; targetSet.set(x - 1); } } void fillCurrentSet(std::bitset<MAX_N>& currentSet, std::vector<std::bitset<MAX_N>> &sets, const InputParams ¶ms) { currentSet = sets[params.n - 1]; } void fillOperations(std::vector<Operation>& operations, std::bitset<MAX_N>& currentSet, std::bitset<MAX_N>& targetSet, std::vector<std::bitset<MAX_N>> &sets, const InputParams ¶ms) { int currentX = params.n; bool isFlipped = false; for(int i = 0; i < params.n; i++) { if(currentSet[i] == targetSet[i]) { continue; } if(currentSet.test(i)) { // flip and do sum addNegOperation(currentSet, operations, currentX); currentX++; addOrOperation(currentSet, sets, operations, currentX, i + 1); currentX++; targetSet.flip(); isFlipped = !isFlipped; } else { // do sum addOrOperation(currentSet, sets, operations, currentX, i + 1); currentX++; } } if(isFlipped) { addNegOperation(currentSet, operations, currentX); } } void printOperations(const std::vector<Operation>& operations) { std::cout << operations.size() << "\n"; for(int i = 0; i < operations.size(); i++) { operations[i].print(); } } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::vector<std::bitset<MAX_N>> sets; sets.reserve(MAX_N); std::bitset<MAX_N> targetSet; std::bitset<MAX_N> currentSet; std::vector<Operation> operations; operations.reserve(MAX_M); InputParams params = loadData(); fillInitialSets(sets, params); loadTargetSet(targetSet, params); fillCurrentSet(currentSet, sets, params); fillOperations(operations, currentSet, targetSet, sets, params); printOperations(operations); return 0; } |