Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Problem: F. Bouncy Ball
- // Contest: Codeforces - Codeforces Round 859 (Div. 4)
- // URL: https://codeforces.com/problemset/problem/1807/F
- // Memory Limit: 256 MB
- // Time Limit: 1000 ms
- //
- // Powered by CP Editor (https://cpeditor.org)
- #include <assert.h>
- #include <bits/stdc++.h>
- using namespace std;
- #ifndef __DEBUG__
- #define dbg(...) 42
- #endif
- template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
- using ll = long long;
- using a2l = array<ll, 2>;
- using pll = pair<ll, ll>;
- using vl = vector<ll>;
- ll fpow(ll b, ll p, ll mod)
- {
- ll ret = 1, cur = b;
- while (p) {
- if (p % 2)
- ret = ret * cur % mod;
- cur = cur * cur % mod;
- p /= 2;
- }
- return ret;
- }
- void solve_overcomplicated()
- {
- ll n, m, i1, j1, i2, j2, ans = LLONG_MAX / 2;
- string d;
- cin >> n >> m >> i1 >> j1 >> i2 >> j2 >> d;
- ll g = gcd(n, m), dx = d[0] == 'D' ? 1 : -1, dy = d[1] == 'L' ? -1 : 1;
- auto find_flip = [&](ll fx, ll fy) {
- ll tx = fx ? n + 1 - i2 : i2;
- ll ty = fy ? m + 1 - j2 : j2;
- ll tg = ((i1 - tx) * dy - (j1 - ty) * dy) / dx / dy;
- if (tg % g != 0)
- return LLONG_MAX;
- ll fn = n / g, fm = m / g, ft = tg / g;
- ll a = ft * fpow(fn, fm - 2, fm) % fm;
- ll b = (a * fn - ft) / fm;
- if (a < 0) {
- ll d = (-a + fm - 1) / fm;
- a += d * fm, b += d * fn;
- }
- if (b < 0) {
- ll d = (-b + fn - 1) / fn;
- a += d * fm, b += d * fn;
- }
- if (a % 2 != fx || b % 2 != fy)
- return LLONG_MAX;
- ll fix = 0;
- return a + b - fix;
- };
- ans = min(ans, find_flip(0, 0));
- ans = min(ans, find_flip(0, 1));
- ans = min(ans, find_flip(1, 0));
- ans = min(ans, find_flip(1, 1));
- cout << (ans == LLONG_MAX / 2 ? -1 : ans) << '\n';
- }
- void solve()
- {
- ll n, m, i1, j1, i2, j2;
- string d;
- cin >> n >> m >> i1 >> j1 >> i2 >> j2 >> d;
- ll dx = d[0] == 'D' ? 1 : -1, dy = d[1] == 'L' ? -1 : 1;
- using a4l = array<ll, 4>;
- set<a4l> vis;
- bool valid = true;
- ll bcnt = 0, x = i1, y = j1;
- vis.insert({x, y, dx, dy});
- while (true) {
- if (x == i2 && y == j2)
- break;
- ll nx = x + dx, ny = y + dy;
- ll bx = (nx == 0) || (nx == n + 1);
- ll by = (ny == 0) || (ny == m + 1);
- dbg(x, y, bx, by);
- if (bx)
- ++bcnt, dx = -dx;
- if (by)
- ++bcnt, dy = -dy;
- bcnt -= bx && by;
- x += dx, y += dy;
- if (x == i2 && y == j2)
- break;
- if (vis.count({x, y, dx, dy})) {
- dbg(x, y, dx, dy);
- valid = false;
- break;
- }
- vis.insert({x, y, dx, dy});
- }
- cout << (valid ? bcnt : -1) << '\n';
- }
- int main(int argc, char **argv)
- {
- ll t;
- cin >> t;
- while (t--)
- solve();
- return 0;
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement