main.cpp (2053B)
1 #include <vector> 2 #include <algorithm> 3 #include <unordered_map> 4 #include <iostream> 5 6 void transform(std::vector<int>& current) { 7 std::vector<int> expanded {}; 8 9 for(int i = 0; i < current.size(); ++i) { 10 for(int x = i+1; x < current.size(); ++x) { 11 12 expanded.push_back(current[i] ^ current[x]); 13 std::push_heap(expanded.begin(), expanded.end()); 14 15 if(expanded.size() > current.size()) { 16 std::pop_heap(expanded.begin(), expanded.end()); 17 } 18 } 19 } 20 sort(expanded.begin(), expanded.end()); 21 for(int i = 0; i < current.size(); ++i) { 22 current[i] = expanded[i]; 23 } 24 } 25 26 27 int score(const std::vector<int>& current) { 28 int max = current[0]; 29 for(auto& val: current) 30 if(val > max) 31 max = val; 32 int min = current[0]; 33 34 for(auto& val: current) 35 if(val < min) 36 min = val; 37 38 return max - min; 39 } 40 41 int main() { 42 43 int problems = 0; 44 std::cin >> problems; 45 46 for(int z = 0; z < problems; ++z) { 47 48 int arrSize, queryCount = 0; 49 std::cin >> arrSize; 50 std::cin >> queryCount; 51 52 std::vector<int> arr {}; 53 for(int i = 0; i < arrSize; ++i) { 54 int current = 0; 55 std::cin >> current; 56 arr.push_back(current); 57 58 } 59 std::unordered_map<int,int> queries {}; 60 for(int i = 0; i < queryCount; ++i) { 61 int current = 0; 62 std::cin >> current; 63 queries[current] = i; 64 } 65 66 int maxCount = 0; 67 68 for(auto& val: queries) { 69 if(val.first > maxCount) { 70 maxCount = val.first; 71 } 72 } 73 74 std::vector<int> results(queryCount,0); 75 76 for(int i = 0; i <= maxCount; ++i) { 77 if(queries.find(i) != queries.end()) { 78 results[queries[i]] = score(arr); 79 } 80 transform(arr); 81 } 82 for(int i = 0; i < results.size(); ++i) { 83 std::cout << results[i] << std::endl; 84 } 85 } 86 }