195292025-12-12 17:12:35TtestCsapatás a lócsapattalcpp17Wrong answer 0/1004ms560 KiB
#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;

// Segédfüggvény a legnagyobb közös osztóhoz (C++17-ben std::gcd is jó, de biztosra megyünk)
long long my_gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

// Struktúra egy intervallum tárolására [start, end]
struct Interval {
    long long start, end;
    bool empty;
};

// Visszaadja a "rossz" intervallumot: azon koordinátákat [0, dim-1]-ben,
// ahonnan NEM lehet 'step' méretűt lépni (sem jobbra, sem balra).
// Rossz, ha: x + step >= dim  ÉS  x - step < 0
Interval get_bad_interval(long long dim, long long step) {
    long long s = max(0LL, dim - step);
    long long e = min(dim - 1, step - 1);
    if (s > e) {
        return {0, 0, true}; // Üres intervallum (nincs rossz mező)
    }
    return {s, e, false};
}

// Két intervallum metszetét vizsgálja. Igaz, ha a metszet NEM üres.
bool intervals_intersect(Interval a, Interval b) {
    if (a.empty || b.empty) return false;
    long long s = max(a.start, b.start);
    long long e = min(a.end, b.end);
    return s <= e;
}

void solve() {
    long long N, M, H, W;
    if (!(cin >> N >> M >> H >> W)) return;

    // 1. Alapesetek
    // Ha 1x1-es a tábla, már ott vagyunk mindenhol.
    if (N == 1 && M == 1) {
        cout << "YES" << endl;
        return;
    }
    // Ha a tábla 1 dimenziós (de nem 1x1), és van bármilyen lépéskényszer (W,H >= 1),
    // akkor nem tudunk elmozdulni a vonalról anélkül, hogy leessünk.
    if (N == 1 || M == 1) {
        cout << "NO" << endl;
        return;
    }

    // 2. Paritás ellenőrzése
    // Ha H+W páros, a (x+y) paritása sosem változik (vagy mindig változik ugyanúgy),
    // így a tábla fele elérhetetlen (mint a futó a sakkban, vagy a huszár, ha nem váltana színt).
    if ((H + W) % 2 == 0) {
        cout << "NO" << endl;
        return;
    }

    // 3. LNKO ellenőrzése
    // Ha gcd(H, W) > 1, akkor a koordináták mindig a gcd többszöröseivel változnak.
    if (my_gcd(H, W) > 1) {
        cout << "NO" << endl;
        return;
    }

    // 4. Szűk sávok (Narrow Strip) ellenőrzése
    // Ha az egyik dimenzióban (pl N) nem tudunk H-t lépni, akkor abban az irányban
    // csak W-t léphetünk. Ez azt jelenti, hogy a MÁSIK dimenzióban (M) mindig H-t kell lépnünk.
    // Ha H > 1, akkor a másik dimenzióban nem érünk el minden sort.
    if (N <= H && H > 1) { cout << "NO" << endl; return; }
    if (N <= W && W > 1) { cout << "NO" << endl; return; }
    if (M <= H && H > 1) { cout << "NO" << endl; return; }
    if (M <= W && W > 1) { cout << "NO" << endl; return; }

    // 5. Izolált mezők (Dead Squares)
    // Megnézzük, vannak-e olyan mezők, ahonnan semelyik típusú ugrás nem hajtható végre.
    // Ugrás 1: x-ben W, y-ban H. (Tiltva, ha x a bad_X_W-ben VAGY y a bad_Y_H-ban van)
    // Ugrás 2: x-ben H, y-ban W. (Tiltva, ha x a bad_X_H-ban VAGY y a bad_Y_W-ben van)

    Interval bx_w = get_bad_interval(N, W); // Rossz X-ek W lépéshez
    Interval bx_h = get_bad_interval(N, H); // Rossz X-ek H lépéshez
    Interval by_w = get_bad_interval(M, W); // Rossz Y-ok W lépéshez
    Interval by_h = get_bad_interval(M, H); // Rossz Y-ok H lépéshez

    // Akkor van baj, ha a két feltételrendszer metszete nem üres.
    // A logikai feltétel: (x in bx_w OR y in by_h) AND (x in bx_h OR y in by_w)
    // Ezt szétbontva 4 eset lehetséges (disztributivitás):

    bool has_isolated = false;

    // Eset 1: x mindkét lépéshez rossz (x in bx_w AND x in bx_h)
    if (intervals_intersect(bx_w, bx_h)) has_isolated = true;

    // Eset 2: y mindkét lépéshez rossz (y in by_h AND y in by_w)
    if (intervals_intersect(by_h, by_w)) has_isolated = true;

    // Eset 3: Ugrás 1 x miatt rossz, Ugrás 2 y miatt rossz (x in bx_w AND y in by_w)
    // Ez egy téglalap alakú terület a táblán. Ha mindkét intervallum létezik, akkor a téglalap létezik.
    if (!bx_w.empty && !by_w.empty) has_isolated = true;

    // Eset 4: Ugrás 1 y miatt rossz, Ugrás 2 x miatt rossz (y in by_h AND x in bx_h)
    if (!by_h.empty && !bx_h.empty) has_isolated = true;

    if (has_isolated) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
}

int main() {
    // Gyors I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    if (cin >> T) {
        while (T--) {
            solve();
        }
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms508 KiB
2Accepted1ms316 KiB
subtask20/22
3Wrong answer3ms316 KiB
4Wrong answer3ms316 KiB
5Wrong answer3ms316 KiB
6Wrong answer3ms316 KiB
7Wrong answer3ms384 KiB
8Wrong answer3ms316 KiB
9Wrong answer3ms316 KiB
10Wrong answer3ms316 KiB
11Wrong answer3ms316 KiB
12Wrong answer3ms316 KiB
13Wrong answer3ms316 KiB
14Wrong answer3ms316 KiB
subtask30/17
15Wrong answer3ms316 KiB
16Wrong answer3ms316 KiB
17Wrong answer3ms316 KiB
18Wrong answer3ms316 KiB
19Wrong answer3ms384 KiB
20Wrong answer3ms316 KiB
21Wrong answer3ms316 KiB
22Wrong answer3ms316 KiB
23Wrong answer3ms316 KiB
24Wrong answer3ms316 KiB
25Wrong answer3ms316 KiB
26Wrong answer3ms316 KiB
27Wrong answer1ms316 KiB
28Wrong answer1ms316 KiB
29Accepted1ms316 KiB
30Wrong answer1ms316 KiB
31Accepted2ms324 KiB
32Accepted1ms552 KiB
33Accepted1ms316 KiB
34Wrong answer1ms316 KiB
35Accepted1ms508 KiB
36Accepted1ms316 KiB
37Accepted1ms500 KiB
38Accepted1ms536 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms316 KiB
41Wrong answer1ms316 KiB
42Wrong answer1ms560 KiB
43Wrong answer1ms316 KiB
44Wrong answer1ms392 KiB
45Wrong answer1ms332 KiB
46Wrong answer1ms316 KiB
47Wrong answer1ms316 KiB
48Wrong answer1ms316 KiB
49Accepted1ms316 KiB
50Accepted1ms316 KiB
subtask40/61
51Accepted3ms508 KiB
52Accepted2ms316 KiB
53Wrong answer3ms316 KiB
54Wrong answer3ms316 KiB
55Wrong answer3ms316 KiB
56Wrong answer3ms316 KiB
57Wrong answer3ms384 KiB
58Wrong answer3ms316 KiB
59Wrong answer3ms316 KiB
60Wrong answer3ms316 KiB
61Wrong answer3ms316 KiB
62Wrong answer3ms316 KiB
63Wrong answer3ms316 KiB
64Wrong answer3ms316 KiB
65Wrong answer1ms316 KiB
66Wrong answer1ms316 KiB
67Accepted1ms316 KiB
68Wrong answer1ms316 KiB
69Accepted2ms324 KiB
70Accepted1ms552 KiB
71Accepted1ms316 KiB
72Wrong answer1ms316 KiB
73Accepted1ms508 KiB
74Accepted1ms316 KiB
75Accepted1ms500 KiB
76Accepted1ms536 KiB
77Wrong answer1ms316 KiB
78Wrong answer1ms316 KiB
79Wrong answer1ms316 KiB
80Wrong answer1ms560 KiB
81Wrong answer1ms316 KiB
82Wrong answer1ms392 KiB
83Wrong answer1ms332 KiB
84Wrong answer1ms316 KiB
85Wrong answer1ms316 KiB
86Wrong answer1ms316 KiB
87Accepted1ms316 KiB
88Accepted1ms316 KiB
89Accepted3ms508 KiB
90Accepted3ms316 KiB
91Accepted3ms316 KiB
92Wrong answer3ms316 KiB
93Accepted3ms316 KiB
94Wrong answer3ms316 KiB
95Accepted3ms316 KiB
96Wrong answer3ms316 KiB
97Accepted3ms344 KiB
98Accepted3ms316 KiB
99Accepted3ms316 KiB
100Accepted3ms316 KiB
101Wrong answer3ms316 KiB
102Wrong answer4ms316 KiB
103Wrong answer3ms316 KiB
104Wrong answer3ms316 KiB
105Wrong answer3ms316 KiB
106Accepted3ms316 KiB
107Accepted4ms316 KiB
108Accepted3ms316 KiB
109Wrong answer3ms316 KiB
110Wrong answer3ms316 KiB
111Wrong answer3ms316 KiB
112Wrong answer3ms316 KiB
113Wrong answer3ms508 KiB
114Wrong answer3ms316 KiB
115Wrong answer3ms316 KiB
116Wrong answer3ms316 KiB
117Wrong answer3ms316 KiB