QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#305875#2567. Hidden RookckisekiAC ✓71ms3964kbC++208.3kb2024-01-16 05:40:162024-01-16 05:40:17

Judging History

This is the latest submission verdict.

  • [2024-01-16 05:40:17]
  • Judged
  • Verdict: AC
  • Time: 71ms
  • Memory: 3964kb
Show
  • [2024-01-16 05:40:16]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

struct R {
    int x1, y1, x2, y2;
};

int dis(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

void solve(int x1, int y1, int x2, int y2, int n, int m) {
    if (x1 == x2 and y1 == y2) {
        printf("! %d %d\n", x1, y1);
        fflush(stdout);
        return;
    }

    int xm = (x1 + x2) / 2, ym = (y1 + y2) / 2;

    if (x1 == x2) {
        int qx1 = x1, qx2 = x2;
        if (qx1 - 1 >= 1) qx1--;
        else qx2++;
        printf("? %d %d %d %d\n", qx1, y1, qx2, ym);
        fflush(stdout);
        int s; scanf("%d", &s);
        if (s == ym - y1 + 1) {
            solve(x1, ym + 1, x2, y2, n, m);
        } else {
            solve(x1, y1, x2, ym, n, m);
        }
        return;
    }
    if (y1 == y2) {
        int qy1 = y1, qy2 = y2;
        if (qy1 - 1 >= 1) qy1--;
        else qy2++;
        printf("? %d %d %d %d\n", x1, qy1, xm, qy2);
        fflush(stdout);
        int s; scanf("%d", &s);
        if (s == xm - x1 + 1) {
            solve(xm + 1, y1, x2, y2, n, m);
        } else {
            solve(x1, y1, xm, y2, n, m);
        }
        return;
    }

    
    R a = {x1, y1, xm, ym};
    R b = {xm + 1, y1, x2, ym};
    R c = {x1, ym + 1, xm, y2};
    R d = {xm + 1, ym + 1, x2, y2};

    int da = dis(a.x1, a.y1, (n + 1) / 2, (m + 1) / 2);
    int db = dis(b.x1, b.y1, (n + 1) / 2, (m + 1) / 2);
    int dc = dis(c.x1, c.y1, (n + 1) / 2, (m + 1) / 2);
    int dd = dis(d.x1, d.y1, (n + 1) / 2, (m + 1) / 2);

    int mxd = min({da, db, dc, dd});
    if (da == mxd) {
        int qx1 = 1, qy1 = 1, qx2 = a.x2, qy2 = a.y2;
        if (qx2 - qx1 == qy2 - qy1) {
            qx1 = 2;
        }
        printf("? %d %d %d %d\n", qx1, qy1, qx2, qy2);
        fflush(stdout);
        int s; scanf("%d", &s);
        if (s == 0) {
            solve(d.x1, d.y1, d.x2, d.y2, n, m);
        } else if (s == qx2 - qx1 + 1) {
            solve(b.x1, b.y1, b.x2, b.y2, n, m);
        } else if (s == qy2 - qy1 + 1) {
            solve(c.x1, c.y1, c.x2, c.y2, n, m);
        } else {
            solve(a.x1, a.y1, a.x2, a.y2, n, m);
        }
    } else if (db == mxd) {
        int qx1 = b.x1, qy1 = 1, qx2 = n, qy2 = b.y2;
        if (qx2 - qx1 == qy2 - qy1) {
            qy1 = 2;
        }
        printf("? %d %d %d %d\n", qx1, qy1, qx2, qy2);
        fflush(stdout);
        int s; scanf("%d", &s);
        if (s == 0) {
            solve(c.x1, c.y1, c.x2, c.y2, n, m);
        } else if (s == qx2 - qx1 + 1) {
            solve(a.x1, a.y1, a.x2, a.y2, n, m);
        } else if (s == qy2 - qy1 + 1) {
            solve(d.x1, d.y1, d.x2, d.y2, n, m);
        } else {
            solve(b.x1, b.y1, b.x2, b.y2, n, m);
        }
    } else if (dc == mxd) {
        int qx1 = 1, qy1 = c.y1, qx2 = c.x2, qy2 = m;
        if (qx2 - qx1 == qy2 - qy1) {
            qx1 = 2;
        }
        printf("? %d %d %d %d\n", qx1, qy1, qx2, qy2);
        fflush(stdout);
        int s; scanf("%d", &s);
        if (s == 0) {
            solve(b.x1, b.y1, b.x2, b.y2, n, m);
        } else if (s == qx2 - qx1 + 1) {
            solve(d.x1, d.y1, d.x2, d.y2, n, m);
        } else if (s == qy2 - qy1 + 1) {
            solve(a.x1, a.y1, a.x2, a.y2, n, m);
        } else {
            solve(c.x1, c.y1, c.x2, c.y2, n, m);
        }
    } else if (dd == mxd) {
        int qx1 = d.x1, qy1 = d.y1, qx2 = n, qy2 = m;
        if (qx2 - qx1 == qy2 - qy1) {
            qx2 = n - 1;
        }
        printf("? %d %d %d %d\n", qx1, qy1, qx2, qy2);
        fflush(stdout);
        int s; scanf("%d", &s);
        if (s == 0) {
            solve(a.x1, a.y1, a.x2, a.y2, n, m);
        } else if (s == qx2 - qx1 + 1) {
            solve(c.x1, c.y1, c.x2, c.y2, n, m);
        } else if (s == qy2 - qy1 + 1) {
            solve(b.x1, b.y1, b.x2, b.y2, n, m);
        } else {
            solve(d.x1, d.y1, d.x2, d.y2, n, m);
        }
    }
}

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        int n, m; scanf("%d %d", &n, &m);

        if (n == 3 and m == 3) {
            int x = 3, y = 3;
            printf("? 1 1 1 3\n");
            fflush(stdout);
            int s1; scanf("%d", &s1);
            if (s1 == 3) x = 1;
            printf("? 1 1 3 1\n");
            fflush(stdout);
            int s2; scanf("%d", &s2);
            if (s2 == 3) y = 1;
            printf("? 2 1 2 3\n");
            fflush(stdout);
            int s3; scanf("%d", &s3);
            if (s3 == 3) x = 2;
            printf("? 1 2 3 2\n");
            fflush(stdout);
            int s4; scanf("%d", &s4);
            if (s4 == 3) y = 2;
            printf("! %d %d\n", x, y);
            fflush(stdout);
            continue;
        }
        if (n == 3 and m == 4) {
            int x = 3;
            printf("? 1 1 1 4\n");
            fflush(stdout);
            int s1; scanf("%d", &s1);
            if (s1 == 4) x = 1;
            printf("? 2 1 2 4\n");
            fflush(stdout);
            int s2; scanf("%d", &s2);
            if (s2 == 4) x = 2;

            solve(x, 1, x, 4, n, m);
            continue;
        }
        if (n == 4 and m == 3) {
            int y = 3;
            printf("? 1 1 4 1\n");
            fflush(stdout);
            int s1; scanf("%d", &s1);
            if (s1 == 4) y = 1;
            printf("? 1 2 4 2\n");
            fflush(stdout);
            int s2; scanf("%d", &s2);
            if (s2 == 4) y = 2;

            solve(1, y, 4, y, n, m);
            continue;
        }

        if (n == 3) {
            int p = (m + 1) / 2;
            printf("? 1 1 2 %d\n", p);
            fflush(stdout);
            int s; scanf("%d", &s);
            if (s == p) {
                //solve(1, 3, p + 1, m, n, m);
                int pp = (p + 1 + m) / 2;
                printf("? 2 1 3 %d\n", pp);
                fflush(stdout);
                scanf("%d", &s);
                if (s == 2) {
                    solve(1, p + 1, 1, pp, n, m);
                } else if (s == pp) {
                    solve(2, pp + 1, 2, m, n, m);
                } else if (s == 0) {
                    solve(1, pp + 1, 1, m, n, m);
                } else {
                    solve(2, p + 1, 2, pp, n, m);
                }
            } else if (s == 0) {
                solve(3, p + 1, 3, m, n, m);
            } else if (s == 2) {
                solve(3, 1, 3, p, n, m);
            } else {
                solve(1, 1, 2, p, n, m);
            }
            continue;
        }
        if (m == 3) {
            int p = (n + 1) / 2;
            printf("? 1 1 %d 2\n", p);
            fflush(stdout);
            int s; scanf("%d", &s);
            if (s == p) {
                //solve(3, 1, m, p + 1, n, m);
                int pp = (p + 1 + n) / 2;
                printf("? 1 2 %d 3\n", pp);
                fflush(stdout);
                scanf("%d", &s);
                if (s == 2) {
                    solve(p + 1, 1, pp, 1, n, m);
                } else if (s == pp) {
                    solve(pp + 1, 2, n, 2, n, m);
                } else if (s == 0) {
                    solve(pp + 1, 1, n, 1, n, m);
                } else {
                    solve(p + 1, 2, pp, 2, n, m);
                }
            } else if (s == 0) {
                solve(p + 1, 3, n, 3, n, m);
            } else if (s == 2) {
                solve(1, 3, p, 3, n, m);
            } else {
                solve(1, 1, p, 2, n, m);
            }
            continue;
        }

        int a = n / 2, b = m / 2;
        if (a == 1) a = 2;
        if (a == b) {
            ++b;
        }
        printf("? 1 1 %d %d\n", a, b);
        fflush(stdout);

        int x1, y1, x2, y2;
        int s; scanf("%d", &s);
        if (s == 0) {
            x1 = a + 1;
            y1 = b + 1;
            x2 = n;
            y2 = m;
        } else if (s == a) {
            x1 = a + 1;
            y1 = 1;
            x2 = n;
            y2 = b;
        } else if (s == b) {
            x1 = 1;
            y1 = b + 1;
            x2 = a;
            y2 = m;
        } else {
            x1 = 1;
            y1 = 1;
            x2 = a;
            y2 = b;
        }

        solve(x1, y1, x2, y2, n, m);
    }
    return 0;
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3892kb

input:

2
6 6
6
3
7
7 5
2
5
0

output:

? 1 1 3 4
? 3 3 5 6
? 2 1 6 3
! 2 3
? 1 1 3 2
? 3 1 7 4
? 2 1 7 3
! 1 4

result:

ok Good (2 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 3964kb

input:

3
15 15
14
10
13
8
3 15
8
13
2
1
15 15
8
22
9
10

output:

? 1 1 7 8
? 5 5 14 15
? 3 7 15 15
? 2 8 15 15
! 2 7
? 1 1 2 8
? 2 1 3 12
? 1 9 2 10
? 1 11 2 11
! 2 12
? 1 1 7 8
? 5 1 15 12
? 7 1 15 10
? 6 1 15 9
! 5 9

result:

ok Good (3 test cases)

Test #3:

score: 0
Accepted
time: 2ms
memory: 3832kb

input:

100
6 6
3
8
6
3 4
1
1
3
2
7 8
4
6
1
5 6
0
0
9 4
4
9
3
1
11 4
5
3
3
1
15 12
7
19
7
7
5 9
2
10
8
6 7
3
5
4
9 9
8
6
6
11 4
5
3
3
1
12 7
3
5
6
14 7
0
11
4
1
9 6
0
11
6
12 11
6
0
11
3 14
7
12
2
1
15 12
0
19
9
10
7 10
3
11
9
15 5
0
0
3
1
11 9
4
8
9
5
14 7
3
10
0
2
15 10
0
11
19
12
7 4
3
5
1
5 13
6
10
3
2
...

output:

? 1 1 3 4
? 1 3 5 6
? 1 1 4 3
! 4 3
? 1 1 1 4
? 2 1 2 4
? 2 1 3 2
? 2 1 3 1
! 3 1
? 1 1 3 4
? 3 1 7 6
? 2 7 3 7
! 3 8
? 1 1 2 3
? 1 1 4 5
! 5 6
? 1 1 4 2
? 1 2 7 4
? 5 1 6 2
? 5 1 5 2
! 6 2
? 1 1 5 2
? 1 2 8 4
? 6 1 7 2
? 6 1 6 2
! 7 1
? 1 1 7 6
? 1 4 11 12
? 1 6 9 12
? 2 5 8 12
! 9 5
? 1 1 2 4
? 1 ...

result:

ok Good (100 test cases)

Test #4:

score: 0
Accepted
time: 2ms
memory: 3916kb

input:

50
9 8
4
7
0
4 11
0
3
3
1
9 11
5
14
0
13 8
4
0
17
4 15
7
0
3
1
8 9
4
0
6
11 12
5
8
0
1
11 14
0
0
22
0
14 14
7
11
20
7
8 3
5
0
2
6 7
6
0
5
4 12
6
3
3
1
6 4
4
4
2
9 15
0
7
0
1
12 7
8
13
2
13 14
6
18
8
7
12 11
0
16
8
2
12 13
6
16
7
0
8 5
5
4
2
8 10
5
13
5
1
13 3
7
0
2
8 10
0
8
13
15 15
0
12
22
20
8 3
5...

output:

? 1 1 4 5
? 1 4 7 8
? 1 1 8 4
! 9 5
? 1 1 2 5
? 1 1 3 8
? 3 6 4 7
? 3 6 4 6
! 4 7
? 1 1 4 5
? 3 1 9 8
? 4 1 9 7
! 3 8
? 1 1 6 4
? 4 1 13 6
? 3 1 13 7
! 3 7
? 1 1 2 7
? 2 1 4 11
? 1 12 2 13
? 1 12 2 12
! 1 13
? 1 1 4 5
? 2 4 6 9
? 2 3 7 9
! 8 3
? 1 1 5 6
? 1 4 8 12
? 1 6 10 12
? 10 4 11 4
! 11 5
? 1 ...

result:

ok Good (50 test cases)

Test #5:

score: 0
Accepted
time: 2ms
memory: 3828kb

input:

50
9 14
4
0
19
1
15 4
8
0
3
2
6 6
4
4
1
10 11
10
0
0
0
10 3
5
0
2
12 13
12
0
10
11
5 15
2
0
2
1
15 9
10
7
16
11 7
3
12
0
3 8
5
2
2
7 7
6
5
2
12 9
4
9
10
11
3 5
3
0
5 3
4
0
2
10 12
6
15
13
1
7 3
2
2
2
11 11
6
8
9
16
15 8
10
16
9
2
11 11
0
16
8
1
7 14
7
5
0
2
9 8
5
7
6
7 6
3
4
5
6 6
3
4
0
15 4
8
0
3
2...

output:

? 1 1 4 7
? 1 5 7 14
? 1 3 8 14
? 7 3 8 3
! 8 4
? 1 1 7 2
? 5 2 15 4
? 1 1 2 2
? 1 1 1 2
! 1 1
? 1 1 3 4
? 3 1 6 5
? 1 4 1 5
! 2 5
? 1 1 5 6
? 4 4 10 11
? 3 3 10 11
? 2 2 10 11
! 1 1
? 1 1 5 2
? 1 2 8 3
? 9 1 9 2
! 9 1
? 1 1 6 7
? 4 5 11 13
? 3 3 12 13
? 2 4 12 13
! 1 4
? 1 1 2 7
? 1 5 4 15
? 4 1 5 ...

result:

ok Good (50 test cases)

Test #6:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

50
14 14
8
10
21
0
6 3
0
2
13 6
0
14
11
1
11 13
6
17
0
2
9 4
5
7
1
10 12
6
15
8
3 12
0
3
3
1
12 5
0
4
3
2
13 4
7
0
2
9 9
0
7
0
10 6
0
5
2
3 5
3
4
6 12
8
12
2
7 9
0
5
5
1
10 11
5
14
7
8 5
5
0
1
5 4
2
4
2
7 5
3
8
1
13 4
7
10
3
1
5 14
2
13
8
1
4 13
6
0
3
1
5 13
2
10
0
2
10 5
0
11
9
2
9 8
0
6
8
4 12
2
9...

output:

? 1 1 7 8
? 5 1 14 11
? 3 1 14 10
? 4 1 14 9
! 3 10
? 1 1 3 2
? 4 2 5 3
! 6 3
? 1 1 6 3
? 1 1 10 5
? 1 1 8 4
? 7 3 7 4
! 8 4
? 1 1 5 6
? 4 1 11 10
? 5 1 11 8
? 3 9 4 9
! 4 9
? 1 1 4 2
? 3 2 9 4
? 1 1 1 2
! 2 2
? 1 1 5 6
? 4 1 10 9
? 5 1 10 8
! 5 9
? 1 1 2 6
? 2 7 3 9
? 2 10 3 11
? 2 10 3 10
! 3 11
?...

result:

ok Good (50 test cases)

Test #7:

score: 0
Accepted
time: 1ms
memory: 3912kb

input:

50
12 15
0
0
23
12
6 7
4
0
2
10 5
2
10
8
11 9
5
7
0
14 5
2
10
3
2
14 8
0
0
13
15 12
6
11
20
12
8 13
9
0
11
1
4 15
2
13
3
2
12 8
0
0
7
1
6 12
0
5
3
1
11 5
5
8
2
13 6
3
14
0
1
11 13
0
8
10
1
9 7
6
0
6
5 13
0
4
3
1
5 6
4
0
1
14 7
0
15
4
1
8 10
8
0
0
2
13 9
9
0
8
10 11
6
9
10
8 10
0
8
13
12 6
3
9
0
1
11...

output:

? 1 1 6 7
? 1 1 9 11
? 1 1 11 13
? 1 1 10 12
! 10 13
? 1 1 3 4
? 3 1 6 6
? 1 6 1 7
! 1 7
? 1 1 5 2
? 4 1 10 4
? 5 1 10 3
! 5 3
? 1 1 5 4
? 1 3 8 9
? 1 2 7 9
! 8 1
? 1 1 7 2
? 5 1 14 4
? 3 1 14 3
? 3 3 3 4
! 3 4
? 1 1 7 4
? 1 1 11 6
? 1 1 13 7
! 14 7
? 1 1 7 6
? 5 1 15 9
? 3 1 15 8
? 4 1 15 7
! 3 7
?...

result:

ok Good (50 test cases)

Test #8:

score: 0
Accepted
time: 2ms
memory: 3956kb

input:

50
11 11
5
14
7
10 11
6
9
6
4 4
0
1
13 12
12
17
6
14 9
10
7
8
12 5
2
9
10
2
14 13
0
20
16
14
4 8
0
8
2
14 15
8
21
0
9
14 3
7
12
2
1
13 10
6
7
0
0
14 10
7
7
8
8
9 6
6
4
6
12 9
9
7
7
2
5 11
0
8
3
2
10 5
0
8
11
12 5
2
12
0
1
12 3
7
0
3
2
12 5
2
9
10
2
8 14
0
16
13
1
4 15
2
3
3
1
10 6
7
7
3
2
9 11
4
0
9...

output:

? 1 1 5 6
? 2 4 8 11
? 1 6 7 11
! 8 6
? 1 1 5 6
? 4 1 10 9
? 5 1 10 10
! 4 10
? 1 1 2 3
? 3 3 3 4
! 4 4
? 1 1 6 7
? 4 5 13 12
? 6 1 13 6
! 6 7
? 1 1 7 4
? 5 3 14 9
? 7 2 13 9
! 7 1
? 1 1 6 2
? 4 1 12 4
? 3 1 12 3
? 1 2 1 3
! 1 3
? 1 1 7 6
? 1 1 11 10
? 1 1 9 8
? 1 1 8 7
! 8 7
? 1 1 2 4
? 1 1 3 6
? 2...

result:

ok Good (50 test cases)

Test #9:

score: 0
Accepted
time: 2ms
memory: 3864kb

input:

50
9 10
4
6
13
8 7
0
5
0
4 12
7
11
2
7 10
0
12
7
14 10
11
7
0
9
3 7
5
0
2
8 15
7
6
7
1
3 14
7
2
2
1
15 3
9
12
3
1
14 3
7
11
2
5 12
2
9
0
2
4 11
6
0
3
1
10 4
0
8
1
10 12
6
7
0
2
11 6
3
8
12
14 7
7
0
6
1
4 12
2
0
3
2
5 12
0
4
3
1
8 11
8
0
15
5 5
2
4
5 8
5
4
1
12 8
4
0
16
3 4
4
1
2
1
11 10
10
8
13
2
3 ...

output:

? 1 1 4 5
? 2 4 7 10
? 1 5 8 10
! 8 5
? 1 1 4 3
? 1 1 6 5
? 1 1 5 6
! 6 7
? 1 1 2 6
? 2 4 4 12
? 1 4 2 5
! 2 6
? 1 1 3 5
? 1 1 5 8
? 1 1 4 7
! 4 8
? 1 1 7 5
? 5 4 14 10
? 7 3 13 10
? 6 2 13 10
! 6 1
? 1 1 2 4
? 2 3 3 7
? 1 1 2 1
! 1 1
? 1 1 4 7
? 3 1 8 11
? 2 1 8 9
? 1 8 2 8
! 1 9
? 1 1 2 7
? 2 1 3 ...

result:

ok Good (50 test cases)

Test #10:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

16
3 3
1
1
3
3
3 3
3
1
1
3
3 3
1
1
3
3
3 3
1
1
3
1
3 3
3
3
1
1
3 3
3
1
1
1
3 3
1
3
1
1
3 3
1
1
1
3
3 3
1
1
1
1
3 4
1
4
3
1
3 4
1
4
2
2
4 3
1
4
3
1
4 3
1
4
2
2
4 3
4
1
3
2
4 4
4
4
1
4 4
0
1

output:

? 1 1 1 3
? 1 1 3 1
? 2 1 2 3
? 1 2 3 2
! 2 2
? 1 1 1 3
? 1 1 3 1
? 2 1 2 3
? 1 2 3 2
! 1 2
? 1 1 1 3
? 1 1 3 1
? 2 1 2 3
? 1 2 3 2
! 2 2
? 1 1 1 3
? 1 1 3 1
? 2 1 2 3
? 1 2 3 2
! 2 3
? 1 1 1 3
? 1 1 3 1
? 2 1 2 3
? 1 2 3 2
! 1 1
? 1 1 1 3
? 1 1 3 1
? 2 1 2 3
? 1 2 3 2
! 1 3
? 1 1 1 3
? 1 1 3 1
? 2 ...

result:

ok Good (16 test cases)

Test #11:

score: 0
Accepted
time: 71ms
memory: 3888kb

input:

15000
12 8
6
0
0
12 15
7
0
0
11
3 9
0
2
1
11 10
10
0
0
9
3 14
2
5
3
2
11 9
8
7
7
14 4
7
3
3
1
8 5
0
4
1
11 10
6
7
15
8 9
4
6
5
5 12
2
4
2
13 9
9
0
0
2
7 13
3
5
13
12 12
6
9
16
0
15 9
4
17
9
14
12 12
7
18
0
1
9 10
5
7
14
1
9 15
7
17
14
1
12 14
12
18
8
1
5 4
2
2
1
15 9
4
0
8
2
14 7
7
5
14
1
8 15
4
6
0...

output:

? 1 1 6 4
? 1 3 9 8
? 1 2 11 8
! 12 1
? 1 1 6 7
? 4 1 12 11
? 3 1 12 13
? 2 1 12 14
! 1 14
? 1 1 2 5
? 2 6 3 7
? 2 8 3 8
! 3 9
? 1 1 5 6
? 4 4 11 10
? 3 3 11 10
? 2 2 11 10
! 2 1
? 1 1 2 7
? 2 1 3 4
? 2 1 3 2
? 2 1 3 1
! 3 1
? 1 1 5 4
? 4 3 11 9
? 5 2 11 9
! 4 2
? 1 1 7 2
? 1 2 11 4
? 8 1 9 2
? 8 1 ...

result:

ok Good (15000 test cases)
English 繁體中文 简体中文

服务器时间: 2025-02-08 16:25:55 | 开源项目