QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#24050#2567. Hidden RookperspectiveAC ✓673ms3672kbC++148.2kb2022-03-25 14:30:402022-04-30 04:49:06

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 04:49:06]
  • 评测
  • 测评结果：AC
  • 用时：673ms
  • 内存：3672kb
查看
  • [2022-03-25 14:30:40]
  • 提交

answer

#pragma comment(linker, "/stack:2000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")

#include <iostream>

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

using namespace std;

int x1, y1, x2, y2;
void change1(int k, int x3, int y3, int dx, int dy){ // Лево верх

   // cerr << "Change1\n";

    cout << "? " << x1 - dx << ' ' << y1 - dy << ' ' << x3 << ' ' << y3  << endl;
    cin >> k;

    if (k == x3 - x1 + 1 + y3 - y1 + dx + dy){
        x2 = x3;
        y2 = y3;
    }
    else if (k == x3 - x1 + 1 + dx && (x3 + 1 >= x1 && x3 + 1 <= x2)){
        x1 = x3 + 1;
        y2 = y3;
    }
    else if (k == y3 - y1 + 1 + dy){
        x2 = x3;
        y1 = y3 + 1;
    }
    else {
        x1 = x3 + 1;
        y1 = y3 + 1;
    }
}

void change2(int k, int x3, int y3, int dx, int dy){ // право низ

  //  cout << "Change2\n";

  //  cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << "      " << x3 << ' ' << y3  << " dxdy " << dx << ' ' << dy<< endl;

    if ((x2 - x1) % 2 == 1)
        x3++;

    if ((y2 - y1) % 2 == 1)
        y3++;


   // cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << "      " << x3 << ' ' << y3  << " dxdy " << dx << ' ' << dy<< endl;

    cout << "? " << x3 << ' ' << y3 << ' ' << x2 + dx << ' ' << y2 + dy << endl;
    cin >> k;
    if ((x2 - x1) % 2 == 1)
        dx--;

    if ((y2 - y1) % 2 == 1)
        dy--;


    if (k == x3 - x1 + 1 + y3 - y1 + dx + dy){
        x1 = x3;
        y1 = y3;
    }
    else if (k == x3 - x1 + 1 + dx){
        x2 = x3 - 1;
        y1 = y3;
    }
    else if (k == y3 - y1 + 1 + dy){
        x1 = x3;
        y2 = y3 - 1;
    }
    else {
        x2 = x3 - 1;
        y2 = y3 - 1;
    }
}

void change3(int k, int x3, int y3, int dx, int dy){

    //cerr << "Change3\n" << x1 << ' ' << y1 << x3 << ' ' << y3  << "   dxdy" << dx << ' ' << dy << endl;

    if ((y2 - y1) % 2 == 1){
        y3++;
    }

    cout << "? " << x1 - dx << ' ' << y3 << ' ' << x3 << ' ' << y2 + dy << endl;
    cin >> k;

    if ((y2 - y1) % 2 == 1){
        dy--;
    }
    if (k == x3 - x1 + 1 + y3 - y1 + dx + dy){
        x2 = x3;
        y1 = y3;
    }
    else if (k == x3 - x1 + 1 + dx){
        x1 = x3 + 1;
        y1 = y3;
    }
    else if (k == y3 - y1 + 1 + dy){
        x2 = x3;
        y2 = y3 - 1;
    }
    else {
        x1 = x3 + 1;
        y2 = y3 - 1;
    }
}

void change4(int k, int x3, int y3, int dx, int dy){
    //cerr << "Change4\n";

    //cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << "      " << x3 << ' ' << y3  << " dxdy " << dx << ' ' << dy<< endl;

    if ((x2 - x1) % 2 == 1)
        x3++;

    cout << "? " << x3 << ' ' << y1 - dy << ' ' << x2 + dx << ' ' << y3 << endl;
    cin >> k;

    //cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << "      " << x3 << ' ' << y3  << " dxdy " << dx << ' ' << dy<< endl;


    if ((x2 - x1) % 2 == 1)
        dx--;

    if (k == x3 - x1 + 1 + y3 - y1 + dx + dy){
        x1 = x3;
        y2 = y3;
    }
    else if (k == x3 - x1 + 1 + dx){
        x2 = x3 = 1;
        y2 = y3;
    }
    else if (k == y3 - y1 + 1 + dy){
        x1 = x3;
        y1 = y3 + 1;
    }
    else {
        x2 = x3 - 1;
        y1 = y3 + 1;
    }
}

int main() {
    int ttt;
    cin >> ttt;
    while(ttt--){
        int n, m;
        cin >> n >> m;

        x1 = y1 = 1;
        x2 = n;
        y2 = m;

        int x3, y3;
        x3 = (x1 + x2) / 2;
        y3 = (y1 + y2) / 2;
        if (x3 - x1 == y3 - y1)
            y3--;
        if (y3 - y1 == 0)
            y3 += 2;

        int k;
        change1(k, x3, y3, 0, 0);

        while (!(x1 == x2 && y1 == y2)){
            int x3, y3;
            x3 = (x1 + x2) / 2;
            y3 = (y1 + y2) / 2;
            //cout << "HAVE " << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << "     " << x3 << ' ' << y3 << endl;

            if (x3 - x1 == y3 - y1){
                if (x3 - x1 == 0){
                    if (x1 > 2 && y1 > 1){
                        change1(k, x3, y3, 2, 1);
                    }
                    else if (x2 + 2 <= n && y2 + 1 <= m){
                        change2(k, x3, y3, 2, 1);
                    }
                    else if (x1 > 2 && y2 + 1 <= m){
                        change3(k, x3, y3, 2, 1);
                    }
                    else if (x2 + 2 <= n && y1 > 1){
                        change4(k, x3, y3, 2, 1);
                    }
                    else if (x1 > 1 && y1 > 2){
                        change1(k, x3, y3, 1, 2);
                    }
                    else if (x2 + 1 <= n && y2 + 2 <= m){
                        change2(k, x3, y3, 1, 2);
                    }
                    else if (x1 > 1 && y2 + 2 <= m){
                        change3(k, x3, y3, 1, 2);
                    }
                    else if (x2 + 1 <= n && y1 > 2){
                        change4(k, x3, y3, 1, 2);
                    }
                    else {
                        if (x1 > 1)
                            change1(k, x3, y3, 1, 0);
                        else
                            change1(k, x3, y3, 0, 1);
                    }
                }

                else if (x1 > 1){
                    change1(k, x3, y3, 1, 0);
                }
                else if (y1 > 1){
                    change1(k, x3, y3, 0, 1);
                }
                else if (x1 == 1 && y1 == 1)
                {
                    change2(k, x3, y3, 1, 0);
                }
            }
            else{
                if (x3 - x1 == 0 && y3 - y1 >= 2){
                    if (x1 > 1){
                        change1(k, x3, y3, 1, 0);
                    }
                    else {
                        change2(k, x3, y3, 1, 0);
                    }
                }
                else if (y3 - y1 == 0 && x3 - x1 >= 2){
                    if (y1 > 1){
                        change1(k, x3, y3, 0, 1);
                    }
                    else {
                        change2(k, x3, y3, 0, 1);
                    }
                }
                else if (x3 - x1 == 0 || y3 - y1 == 0){
                    if (x3 - x1 == 0 && x1 > 2){
                        change1(k, x3, y3, 2, 0);
                    }
                    else if (x3 - x1 == 0 && x2 + 2 <= n){
                        change2(k, x3, y3, 2, 0);
                    }
                    else if (y3 - y1 == 0 && y1 > 2){
                        change1(k, x3, y3, 0, 2);
                    }
                    else if (y3 - y1 == 0 && y2 + 2 <= m){
                        change2(k, x3, y3, 0, 2);
                    }
                    else if (x1 > 1 && y1 > 1){
                        change1(k, x3, y3, 1, 1);
                    }
                    else if (x2 + 1 <= n && y2 + 1 <= m){
                        change2(k, x3, y3, 1, 1);
                    }
                    else if (x1 > 1 && y2 + 1 <= m){
                        change3(k, x3, y3, 1, 1);
                    }
                    else if (x2 + 1 <= n && y1 > 1){
                        change4(k, x3, y3, 1, 1);
                    }
                    else{
                      //  cout << "!!!\n";

                        if (x2 - x1 == 0 && x1 > 1)
                            change1(k, x3, y3, 1, 0);
                        else if (x2 - x1 == 0)
                            change2(k, x3, y3, 1, 0);
                        else if (y2 - y1 == 0 && y1 > 1)
                            change1(k, x3, y3, 0, 1);
                        else if (y2 - y1 == 0)
                            change2(k, x3, y3, 0, 1);
                        else{
                            y3++;
                            change1(k, x3, y3, 0, 0);
                        }
                    }
                }
                else{
                    change1(k, x3, y3, 0, 0);
                }
            }
        }

        cout << "! " << x1 << ' ' << y1 << endl;
    }

    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3588kb

input:

2
6 6
2
4
2
7 5
3
4
3

output:

? 1 1 3 2
? 1 2 2 4
? 2 4 4 5
! 2 3
? 1 1 4 3
? 1 2 2 4
? 2 4 4 5
! 1 4

result:

ok ok  Good (2 test cases)

Test #2:

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

input:

3
15 15
14
5
3
4
3 15
8
5
4
4
15 15
7
4
4
2

output:

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

result:

ok ok  Good (3 test cases)

Test #3:

score: 0
Accepted
time: 36ms
memory: 3540kb

input:

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

output:

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

result:

ok ok  Good (100 test cases)

Test #4:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

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

output:

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

result:

ok ok  Good (50 test cases)

Test #5:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

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

output:

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

result:

ok ok  Good (50 test cases)

Test #6:

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

input:

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

output:

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

result:

ok ok  Good (50 test cases)

Test #7:

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

input:

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

output:

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

result:

ok ok  Good (50 test cases)

Test #8:

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

input:

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

output:

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

result:

ok ok  Good (50 test cases)

Test #9:

score: 0
Accepted
time: 3ms
memory: 3452kb

input:

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

output:

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

result:

ok ok  Good (50 test cases)

Test #10:

score: 0
Accepted
time: 8ms
memory: 3588kb

input:

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

output:

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

result:

ok ok  Good (16 test cases)

Test #11:

score: 0
Accepted
time: 673ms
memory: 3656kb

input:

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

output:

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

result:

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

Server Time: 2025-02-01 20:41:25 | OpenSource Project