algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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 }