Advertisement
Korotkodul

N4 send

Oct 25th, 2022
649
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.36 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int, int>
  11. #define pb(x) push_back(x)
  12. #include <ctime>
  13. using namespace std;
  14. using ll = long long;
  15. using ld = long double;
  16. using db = double;
  17. void cv(vector <int> &v) {
  18.     for (auto x : v) cout << x << ' ';
  19.     cout << "\n";
  20. }
  21.  
  22. void cvl(vector <ll> &v) {
  23.     for (auto x : v) cout << x << ' ';
  24.     cout << "\n";
  25. }
  26.  
  27.  
  28. void cvv(vector <vector <int> > &v) {
  29.     for (auto x : v) cv(x);
  30.     cout << "\n";
  31. }
  32.  
  33. void cvb(vector <bool> v) {
  34.     for (bool x : v) cout << x << ' ';
  35.     cout << "\n";
  36. }
  37.  
  38. void cvs(vector <string>  v) {
  39.     for (auto a : v) {
  40.         cout << a << "\n";
  41.     }
  42. }
  43.  
  44. void cvp(vector <pii> a) {
  45.     for (auto p : a) {
  46.         cout << p.first << ' ' << p.second << "\n";
  47.     }
  48.     cout << "\n";
  49. }
  50.  
  51. ll S(ll a1, ll d, ll n) {
  52.     return (2 * a1 + d * (n - 1) ) * n / 2;
  53. }
  54.  
  55.  
  56. ll frx, tox, fry, toy;
  57.  
  58. bool ok(int i, int j) {
  59.     return i >= frx && i <= tox && j >= fry && j <= toy;
  60. }
  61. vector <int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
  62.  
  63. bool sh = 0;
  64. ll n, m;
  65. // 10 11
  66. /*
  67. 1000000000
  68. 1000000000
  69. */
  70. ll dull () {
  71.     ios::sync_with_stdio(0);
  72.     cin.tie(0);
  73.     cout.tie(0);
  74.     frx = -2;
  75.     tox = n - 1;
  76.     fry = 0;
  77.     toy = m - 1;
  78.     ll cnt = 1;
  79.     vector <vector <int> > a(n, vector <int> (m, 0));
  80.     /*if (min(n, m) == 1) {
  81.         cout << n * m;
  82.         exit(0);
  83.     }*/
  84.     a[0][0] = 1;
  85.     int i = 0, j = 0, to = 0;
  86.     ll k = 0;
  87.     while (1) {
  88.         //cnt +=
  89.         while ( ok(i + dx[to], j + dy[to]) ) {
  90.             i += dx[to];
  91.             j += dy[to];
  92.             a[i][j] = 1;
  93.             cnt++;
  94.         }
  95.         /*if (sh) {
  96.             cout << "to = " << to << "\n";
  97.             cout << "frx tox = " << frx << ' ' << tox << "\n";
  98.             cout << "fry toy = " << fry << ' ' << toy << "\n";
  99.         }*/
  100.         k++;
  101.         if (to == 0) {
  102.             frx += 2;
  103.             //tox -= 2;
  104.         }
  105.         else if (to == 2) {
  106.             tox -= 2;
  107.         }
  108.         else if (to == 1) {
  109.             fry += 2;
  110.         }
  111.         else if (to == 3) {
  112.             toy -= 2;
  113.         }
  114.         to++;
  115.         to %= 4;
  116.         /*if (sh) {
  117.             cout << "to = " << to << "\n";
  118.             cout << "i + dx[to] j + dy[to] = " << i + dx[to] << ' ' << j + dy[to] << "\n";
  119.         }*/
  120.         if (!ok(i + dx[to], j + dy[to])) {
  121.             break;
  122.         }
  123.     }
  124.     /*if (sh) {
  125.         cout << "i j = " << i << ' ' << j << "\n";
  126.         cout << "to = " << to << "\n";
  127.         cout << "ans\n";
  128.     }*/
  129.  
  130.     if (sh) {
  131.         cvv(a);
  132.     }
  133.     if (sh) {
  134.         cout << "dull k = " << k << "\n\n\n";
  135.     }
  136.     return cnt;
  137. }
  138.  
  139. bool ok(ll k) {
  140.     ll resx, resy;
  141.     ll gox = k / 2 + k % 2;
  142.     if (gox == 1) {
  143.         resx = n;
  144.     } else {
  145.         resx = n - (1 + 2 * (gox - 2));
  146.     }
  147.  
  148.     ll goy = k / 2;
  149.     resy = m - (1 + 2 * (goy - 1));
  150.     if (sh) {
  151.         cout << "check\n";
  152.         cout << "k = " << k << "\n";
  153.         cout << "gox goy = " << gox << ' ' << goy << "\n";
  154.         cout << "resx resy = " << resx << ' ' << resy << "\n";
  155.         cout << "\n";
  156.     }
  157.  
  158.     if (k % 2 == 0 && resx < 2) {
  159.         return 0;
  160.     }
  161.     if (k % 2 == 1 && resy < 2) {
  162.         return 0;
  163.     }
  164.  
  165.     bool r = min(resy, resx) >= 0;
  166.     return r;
  167. }
  168.  
  169. ll get(ll k) {
  170.     ll gox = k / 2 + k % 2;
  171.     ll goy = k / 2;
  172.     ll Sn, Sm;
  173.     Sn = S(n - 1, -2, gox - 1) + n;
  174.     Sm = S(m - 1, -2, goy);
  175.     ll r = Sn + Sm;
  176.     if (sh) {
  177.         cout << "get\n";
  178.         cout << "gox goy = " << gox << ' ' << goy << "\n";
  179.         cout << "Sn Sm = " << Sn << ' ' << Sm << "\n";
  180.         cout << "r = " << r << "\n";
  181.     }
  182.  
  183.     return r;
  184. }
  185.  
  186. ll my() {
  187.     if (min(n, m) == 1) {
  188.         return n * m;
  189.     }
  190.     ll L = 0, R = max(n, m) * 2, med;
  191.     while (L + 1 < R) {
  192.         med = (L + R) / 2;
  193.         if (sh) {
  194.             cout << "med = " << med << "\n";
  195.         }
  196.         if (ok(med)) {
  197.             L = med;
  198.         } else {
  199.             R = med;
  200.         }
  201.     }
  202.  
  203.     if (sh) {
  204.         cout << "L = " << L << "\n";
  205.         cout << "\n\n";
  206.     }
  207.  
  208.     ll ans = get(L);
  209.     return ans;
  210. }
  211.  
  212. bool random = 1;
  213. // 10 20
  214. int main() {
  215.     cin >> n >> m;
  216.     ll ans = my();
  217.     cout << ans;
  218. }
  219.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement