Advertisement
pb_jiang

CF1807F

Mar 25th, 2025
540
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.94 KB | None | 0 0
  1. // Problem: F. Bouncy Ball
  2. // Contest: Codeforces - Codeforces Round 859 (Div. 4)
  3. // URL: https://codeforces.com/problemset/problem/1807/F
  4. // Memory Limit: 256 MB
  5. // Time Limit: 1000 ms
  6. //
  7. // Powered by CP Editor (https://cpeditor.org)
  8.  
  9. #include <assert.h>
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12. #ifndef __DEBUG__
  13. #define dbg(...) 42
  14. #endif
  15. template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
  16.  
  17. using ll = long long;
  18. using a2l = array<ll, 2>;
  19. using pll = pair<ll, ll>;
  20. using vl = vector<ll>;
  21.  
  22. ll fpow(ll b, ll p, ll mod)
  23. {
  24.     ll ret = 1, cur = b;
  25.     while (p) {
  26.         if (p % 2)
  27.             ret = ret * cur % mod;
  28.         cur = cur * cur % mod;
  29.         p /= 2;
  30.     }
  31.     return ret;
  32. }
  33.  
  34. void solve_overcomplicated()
  35. {
  36.     ll n, m, i1, j1, i2, j2, ans = LLONG_MAX / 2;
  37.     string d;
  38.     cin >> n >> m >> i1 >> j1 >> i2 >> j2 >> d;
  39.     ll g = gcd(n, m), dx = d[0] == 'D' ? 1 : -1, dy = d[1] == 'L' ? -1 : 1;
  40.  
  41.     auto find_flip = [&](ll fx, ll fy) {
  42.         ll tx = fx ? n + 1 - i2 : i2;
  43.         ll ty = fy ? m + 1 - j2 : j2;
  44.         ll tg = ((i1 - tx) * dy - (j1 - ty) * dy) / dx / dy;
  45.         if (tg % g != 0)
  46.             return LLONG_MAX;
  47.         ll fn = n / g, fm = m / g, ft = tg / g;
  48.         ll a = ft * fpow(fn, fm - 2, fm) % fm;
  49.         ll b = (a * fn - ft) / fm;
  50.         if (a < 0) {
  51.             ll d = (-a + fm - 1) / fm;
  52.             a += d * fm, b += d * fn;
  53.         }
  54.         if (b < 0) {
  55.             ll d = (-b + fn - 1) / fn;
  56.             a += d * fm, b += d * fn;
  57.         }
  58.         if (a % 2 != fx || b % 2 != fy)
  59.             return LLONG_MAX;
  60.  
  61.         ll fix = 0;
  62.         return a + b - fix;
  63.     };
  64.  
  65.     ans = min(ans, find_flip(0, 0));
  66.     ans = min(ans, find_flip(0, 1));
  67.     ans = min(ans, find_flip(1, 0));
  68.     ans = min(ans, find_flip(1, 1));
  69.     cout << (ans == LLONG_MAX / 2 ? -1 : ans) << '\n';
  70. }
  71.  
  72. void solve()
  73. {
  74.     ll n, m, i1, j1, i2, j2;
  75.     string d;
  76.     cin >> n >> m >> i1 >> j1 >> i2 >> j2 >> d;
  77.     ll dx = d[0] == 'D' ? 1 : -1, dy = d[1] == 'L' ? -1 : 1;
  78.     using a4l = array<ll, 4>;
  79.     set<a4l> vis;
  80.     bool valid = true;
  81.     ll bcnt = 0, x = i1, y = j1;
  82.     vis.insert({x, y, dx, dy});
  83.     while (true) {
  84.         if (x == i2 && y == j2)
  85.             break;
  86.         ll nx = x + dx, ny = y + dy;
  87.         ll bx = (nx == 0) || (nx == n + 1);
  88.         ll by = (ny == 0) || (ny == m + 1);
  89.         dbg(x, y, bx, by);
  90.         if (bx)
  91.             ++bcnt, dx = -dx;
  92.         if (by)
  93.             ++bcnt, dy = -dy;
  94.         bcnt -= bx && by;
  95.  
  96.         x += dx, y += dy;
  97.         if (x == i2 && y == j2)
  98.             break;
  99.         if (vis.count({x, y, dx, dy})) {
  100.             dbg(x, y, dx, dy);
  101.             valid = false;
  102.             break;
  103.         }
  104.         vis.insert({x, y, dx, dy});
  105.     }
  106.     cout << (valid ? bcnt : -1) << '\n';
  107. }
  108.  
  109. int main(int argc, char **argv)
  110. {
  111.     ll t;
  112.     cin >> t;
  113.     while (t--)
  114.         solve();
  115.     return 0;
  116. };
  117.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement