QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54245#4575. Interactive Treasure Huntnot_so_organic#WA 20ms3720kbC++232.8kb2022-10-07 17:07:522022-10-07 17:07:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-07 17:07:54]
  • 评测
  • 测评结果:WA
  • 用时:20ms
  • 内存:3720kb
  • [2022-10-07 17:07:52]
  • 提交

answer

#include <bits/stdc++.h>
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define int long long
#define inf 1e18
using namespace std;
const int maxn = 1000005; // REMEMBER TO CHANGE UPPER BOUND
int mod = 1000000007, mod2 = 998244353, n, fac[maxn + 5], invfac[maxn + 5], arr[maxn + 5];
void mod998() {swap(mod, mod2);}
bool isprime(int k) {
    for(int i = 2; i * i <= k; i++) if(k % i == 0) return false; 
    return true;
}
int bm(int a, int b) {
    if(b == 0) return 1; 
    int t = bm(a, b / 2); 
    return (b % 2 == 1 ? t * t % mod * a % mod : t * t % mod);
}
int inv(int a) {return bm(a, mod - 2);}
int ncr(int n, int r) {
    return (r > n ? 0LL : fac[n] * invfac[r] % mod * invfac[n - r] % mod);
}
void pre_fac(int n) {
    fac[0] = 1; for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
}
void pre_invfac(int n) {
    for(int i = 0; i <= n; i++) invfac[i] = inv(fac[i]);
}
int ask(int x, int y) {
    cout << "SCAN " << x << ' ' << y << endl;
    int a;
    cin >> a;
    return a;
}
int dist(int x1, int y1, int x2, int y2, int xx, int yy) {
    return abs(x1 - xx) + abs(y1 - yy) + abs(x2 - xx) + abs(y2 - yy);
}
void solve(int TC) {
    // cin >> n;
    // for(int i = 1; i <= n; i++) cin >> arr[i]; // 1 BASED!!
    int n, m;
    cin >> n >> m;
    int tl = ask(1, 1);
    int tr = ask(1, m);
    int avd = (tl + tr - (m - 1) * 2) / 2;
    int mm = (tl - avd) / 2;
    avd /= 2;
    avd++; mm++;
    int tm = ask(avd, mm);
    int mmm = min(m, mm + tm / 2);
    int tmm = ask(avd, mmm);
    set<pair<pair<int, int>, pair<int, int>>> poss;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            for(int ii = 1; ii <= n; ii++) {
                for(int jj = 1; jj <= m; jj++) {
                    if(ii == i && jj == j) continue;
                    if(tl != dist(i, j, ii, jj, 1, 1)) continue;
                    if(tr != dist(i, j, ii, jj, 1, m)) continue;
                    if(tm != dist(i, j, ii, jj, avd, mm)) continue;
                    if(tmm != dist(i, j, ii, jj, avd, mmm)) continue;
                    poss.insert(mp(mp(ii, jj), mp(i, j)));
                }
            }
        }
    }
    // assert(poss.size() <= 4);
    int lef = 2;
    for(auto x: poss) {
        cout << "DIG " << x.fi.fi << ' ' << x.fi.se << endl;
        int a;
        cin >> a;
        if(a == 0) continue;
        lef -= a;
        cout << "DIG " << x.se.fi << ' ' << x.se.se << endl;
        cin >> a;
        if(a == 0) continue;
        lef -= a;
        if(lef == 0) return;
    }
}
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t = 1;  
    cin >> t; // REMOVE THIS LINE IF ONLY 1 CASE
    for(int i = 1; i <= t; i++) solve(i);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
2 3
3
1
1
1
1
1

output:

SCAN 1 1
SCAN 1 3
SCAN 1 2
SCAN 1 2
DIG 1 2
DIG 1 3

result:

ok (1 test case)

Test #2:

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

input:

72
3 3
1
5
1
1
1
1
3 3
4
4
4
4
0
1
1
3 3
5
5
3
3
0
1
1
3 2
2
4
2
4
1
1
3 3
5
1
1
1
1
1
3 2
3
3
3
3
1
1
3 3
4
4
2
4
1
1
2 3
3
3
3
3
1
1
3 3
3
5
1
1
1
1
3 3
1
3
1
1
1
1
3 3
3
3
3
3
0
1
1
2 3
3
3
3
3
0
1
1
3 2
1
1
1
1
1
1
3 2
4
4
2
2
1
1
2 3
3
3
1
1
1
1
3 3
4
2
2
2
0
1
1
2 3
3
1
1
1
1
1
3 3
2
4
2
2
0
1...

output:

SCAN 1 1
SCAN 1 3
SCAN 1 1
SCAN 1 1
DIG 1 1
DIG 2 1
SCAN 1 1
SCAN 1 3
SCAN 2 2
SCAN 2 3
DIG 1 1
DIG 1 3
DIG 3 1
SCAN 1 1
SCAN 1 3
SCAN 2 2
SCAN 2 3
DIG 2 1
DIG 2 3
DIG 3 1
SCAN 1 1
SCAN 1 2
SCAN 2 1
SCAN 2 2
DIG 1 1
DIG 3 1
SCAN 1 1
SCAN 1 3
SCAN 1 3
SCAN 1 3
DIG 1 3
DIG 2 3
SCAN 1 1
SCAN 1 2
SCAN 2...

result:

ok (72 test cases)

Test #3:

score: 0
Accepted
time: 10ms
memory: 3648kb

input:

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

output:

SCAN 1 1
SCAN 1 16
SCAN 1 8
SCAN 1 15
DIG 1 1
DIG 1 15
DIG 2 1
SCAN 1 1
SCAN 1 4
SCAN 1 3
SCAN 1 4
DIG 1 3
DIG 1 4
DIG 2 3
SCAN 1 1
SCAN 1 15
SCAN 1 9
SCAN 1 10
DIG 1 9
DIG 2 10
SCAN 1 1
SCAN 1 5
SCAN 2 1
SCAN 2 1
DIG 2 1
DIG 2 2
SCAN 1 1
SCAN 1 13
SCAN 2 7
SCAN 2 13
DIG 2 1
DIG 2 13
SCAN 1 1
SCAN 1...

result:

ok (100 test cases)

Test #4:

score: 0
Accepted
time: 6ms
memory: 3624kb

input:

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

output:

SCAN 1 1
SCAN 1 2
SCAN 3 2
SCAN 3 2
DIG 2 2
DIG 4 2
SCAN 1 1
SCAN 1 2
SCAN 8 2
SCAN 8 2
DIG 8 2
DIG 9 2
SCAN 1 1
SCAN 1 2
SCAN 5 1
SCAN 5 2
DIG 2 1
DIG 9 1
SCAN 1 1
SCAN 1 2
SCAN 6 1
SCAN 6 1
DIG 6 1
DIG 6 2
SCAN 1 1
SCAN 1 2
SCAN 8 2
SCAN 8 2
DIG 3 2
DIG 13 2
SCAN 1 1
SCAN 1 2
SCAN 4 1
SCAN 4 2
DIG...

result:

ok (100 test cases)

Test #5:

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

input:

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

output:

SCAN 1 1
SCAN 1 10
SCAN 3 4
SCAN 3 6
DIG 3 2
DIG 3 7
SCAN 1 1
SCAN 1 12
SCAN 2 11
SCAN 2 12
DIG 1 10
DIG 1 12
DIG 3 10
SCAN 1 1
SCAN 1 13
SCAN 3 9
SCAN 3 11
DIG 3 7
DIG 3 11
SCAN 1 1
SCAN 1 4
SCAN 2 2
SCAN 2 4
DIG 2 1
DIG 3 4
SCAN 1 1
SCAN 1 10
SCAN 2 4
SCAN 2 6
DIG 1 3
DIG 1 6
DIG 3 3
SCAN 1 1
SCAN...

result:

ok (100 test cases)

Test #6:

score: 0
Accepted
time: 20ms
memory: 3564kb

input:

100
7 3
10
14
2
4
1
1
5 3
6
4
4
4
0
1
1
5 3
6
10
2
4
1
1
6 3
9
9
3
3
1
1
6 3
7
3
3
3
1
1
10 3
11
11
7
7
1
1
15 3
31
29
1
1
1
1
16 3
12
10
10
10
0
1
1
11 3
9
9
7
7
1
1
15 3
27
23
3
3
1
1
6 3
6
8
6
8
1
1
12 3
18
14
8
8
1
1
4 3
3
7
1
1
1
1
14 3
18
16
10
10
0
1
1
8 3
11
11
1
1
1
1
16 3
11
13
3
3
0
1
1
1...

output:

SCAN 1 1
SCAN 1 3
SCAN 6 1
SCAN 6 2
DIG 5 1
DIG 7 1
SCAN 1 1
SCAN 1 3
SCAN 2 2
SCAN 2 3
DIG 1 2
DIG 1 3
DIG 4 2
SCAN 1 1
SCAN 1 3
SCAN 4 1
SCAN 4 2
DIG 3 1
DIG 5 1
SCAN 1 1
SCAN 1 3
SCAN 4 2
SCAN 4 3
DIG 4 1
DIG 5 3
SCAN 1 1
SCAN 1 3
SCAN 2 3
SCAN 2 3
DIG 1 3
DIG 4 3
SCAN 1 1
SCAN 1 3
SCAN 5 2
SCAN ...

result:

ok (100 test cases)

Test #7:

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

input:

100
10 6
15
15
1
1
1
1
4 8
1
13
1
1
1
1
2 2
1
1
1
1
1
1
15 6
10
6
6
6
0
1
1
7 4
3
7
3
3
1
1
4 4
7
9
3
3
0
1
1
12 10
26
26
6
8
1
1
11 3
8
10
8
10
1
1
6 11
16
14
4
4
0
1
1
3 11
17
9
7
7
0
1
1
7 8
12
14
8
12
1
1
16 12
16
20
10
14
0
1
1
15 11
19
17
9
15
1
1
16 9
16
20
2
2
1
1
4 16
6
28
6
8
1
1
8 9
19
19...

output:

SCAN 1 1
SCAN 1 6
SCAN 6 3
SCAN 6 3
DIG 6 3
DIG 6 4
SCAN 1 1
SCAN 1 8
SCAN 1 1
SCAN 1 1
DIG 1 1
DIG 1 2
SCAN 1 1
SCAN 1 2
SCAN 1 1
SCAN 1 1
DIG 1 1
DIG 1 2
SCAN 1 1
SCAN 1 6
SCAN 2 4
SCAN 2 6
DIG 1 3
DIG 1 6
DIG 4 3
SCAN 1 1
SCAN 1 4
SCAN 2 1
SCAN 2 2
DIG 1 1
DIG 3 2
SCAN 1 1
SCAN 1 4
SCAN 3 2
SCAN ...

result:

ok (100 test cases)

Test #8:

score: -100
Wrong Answer
time: 13ms
memory: 3720kb

input:

100
11 15
20
12
10
12
0
1
1
15 11
10
30
10
20
1
1
16 13
15
17
7
7
1
1
11 16
30
26
16
20
1
1
10 12
21
31
3
3
1
1
15 11
21
33
13
23
0
1
1
13 13
31
31
11
13
0
1
1
15 14
19
33
5
9
1
1
14 10
34
36
4
4
1
1
14 15
23
19
7
7
0
1
1
11 13
25
21
15
19
0
1
1
14 15
35
35
15
19
1
1
15 15
27
27
15
23
0
1
1
11 11
21...

output:

SCAN 1 1
SCAN 1 15
SCAN 2 10
SCAN 2 15
DIG 1 6
DIG 1 14
DIG 3 6
SCAN 1 1
SCAN 1 11
SCAN 6 1
SCAN 6 6
DIG 1 1
DIG 11 1
SCAN 1 1
SCAN 1 13
SCAN 3 6
SCAN 3 9
DIG 2 4
DIG 4 9
SCAN 1 1
SCAN 1 16
SCAN 7 9
SCAN 7 16
DIG 4 5
DIG 11 14
SCAN 1 1
SCAN 1 12
SCAN 8 4
SCAN 8 5
DIG 8 3
DIG 9 5
SCAN 1 1
SCAN 1 11
S...

result:

wrong answer Asked more than 7 queries (test case 19)