mfgnik

Untitled

Jan 16th, 2021
531
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <limits>
  4. #include <cstdlib>
  5.  
  6. using namespace std;
  7.  
  8.  
  9. int64_t CalculateAll(int64_t m, int64_t n) {
  10.     return (1 + m * n) * m * n / 2;
  11. }
  12.  
  13. int64_t CalculateHorizontal(int64_t m, int64_t n, int64_t k) {
  14.     int64_t first_half = (1 + k*m) * k*m / 2;
  15.     return first_half;
  16. }
  17.  
  18. int64_t CalculateHorizontalDiff(int64_t m, int64_t n, int64_t k) {
  19.     int64_t first_half = (1 + k*m) * k*m / 2;
  20.     return abs(2 * first_half - CalculateAll(m, n));
  21. }
  22.  
  23. int64_t CalculateVertically(int64_t m, int64_t n, int64_t k) {
  24.     int64_t first_column = (1  + m * (n - 1) + 1) * n / 2;
  25.     int64_t first_half = first_column * k + k * (k - 1) / 2 * n;
  26.     return first_half;
  27. }
  28.  
  29. int64_t CalculateVerticallyDiff(int64_t m, int64_t n, int64_t k) {
  30.     int64_t first_column = (1  + m * (n - 1) + 1) * n / 2;
  31.     int64_t first_half = first_column * k + k * (k - 1) / 2 * n;
  32.     return abs(2 * first_half - CalculateAll(m, n));
  33. }
  34.  
  35. int main() {
  36.     int t;
  37.     std::cin >> t;
  38.     while (t--) {
  39.         int64_t m, n, one = 1;
  40.         std::cin >> n >> m;
  41.         int64_t horizontal_result = std::numeric_limits<int64_t>::max();
  42.         int64_t vertical_result = std::numeric_limits<int64_t>::max();
  43.         int64_t min_horizontal = 0, min_vertically = 0;
  44.         int64_t all_sum = CalculateAll(m, n);
  45.         int64_t left = 0, right = n - 1;
  46.         while (right - left > 1) {
  47.             int64_t median = (left + right) / 2;
  48.             int64_t new_horizontal = CalculateHorizontal(m , n, median);
  49.             if (2 * new_horizontal > all_sum) {
  50.                 right = median;
  51.             } else {
  52.                 left = median;
  53.             }
  54.         }
  55.         for (int64_t k = std::max(one, left - 1); k < std::min(n, right + 1); ++k) {
  56.             int64_t new_horizontal = CalculateHorizontalDiff(m , n, k);
  57.  
  58.             if (new_horizontal < horizontal_result) {
  59.                 horizontal_result = new_horizontal;
  60.                 min_horizontal = k;
  61.             }
  62.         }
  63.         left = 0, right = m - 1;
  64.         while (right - left > 1) {
  65.             int64_t median = (left + right) / 2;
  66.             int64_t new_vertical = CalculateVertically(m , n, median);
  67.             if (2 * new_vertical > all_sum) {
  68.                 right = median;
  69.             } else {
  70.                 left = median;
  71.             }
  72.         }
  73.         for (int64_t k = std::max(one, left - 1); k < std::min(right + 1, m); ++k) {
  74.             int64_t new_vertical = CalculateVerticallyDiff(m , n, k);
  75.             if (new_vertical < vertical_result) {
  76.                 vertical_result = new_vertical;
  77.                 min_vertically = k;
  78.             }
  79.         }
  80.         if (vertical_result < horizontal_result) {
  81.             std::cout << "V " << min_vertically + 1 << "\n";
  82.         } else {
  83.             std::cout << "H " << min_horizontal + 1 << "\n";
  84.         }
  85.     }
  86. }
  87.  
RAW Paste Data