QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#376160#4575. Interactive Treasure HuntInfinityNS#AC ✓16ms4068kbC++233.8kb2024-04-03 22:24:122024-04-03 22:24:12

Judging History

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

  • [2024-04-03 22:24:12]
  • 评测
  • 测评结果：AC
  • 用时：16ms
  • 内存：4068kb
查看
  • [2024-04-03 22:24:12]
  • 提交

answer

#include<bits/stdc++.h>
#define sz(x) (int)(x).size()
#define f first
#define s second
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
mt19937 rng(1);

pair<pair<int,int>,pair<int,int>> target;
int dist(pair<int,int> a,pair<int,int> b){
    return abs(a.f-b.f)+abs(a.s-b.s);
}
bool my=0;
int scan(int x,int y){
    if(my){
        return dist({x,y},target.f)+dist({x,y},target.s);
    }
    printf("SCAN %i %i\n",x,y);
    fflush(stdout);
    int d;
    scanf("%i",&d);
    return d;
}
bool dig(int x,int y){
    if(my){
        return true;
    }
    printf("DIG %i %i\n",x,y);
    fflush(stdout);
    int d;
    scanf("%i",&d);
    return d;
}
int n,m;
pair<int,int> ans;
int startk;
const int N=64;
int cnt[N];
bool solve(vector<pair<pair<int,int>,pair<int,int>>> &targets,int k){
    if(sz(targets)<=2)return true;
    if(k==0)return false;
    vector<pair<int,pair<int,int>>>  tt;
    for(int x=1;x<=n;x++){
        for(int y=1;y<=m;y++){
            for(int j=0;j<N;j++)cnt[j]=0;
            for(auto p:targets){
                int dd=dist({x,y},p.f)+dist({x,y},p.s);
                cnt[dd]++;
            }
            int mx=0;
            for(int j=0;j<N;j++){
                mx=max(mx,cnt[j]);
            }
            tt.pb({mx,{x,y}});
        }
    }
    sort(all(tt));
    ans=tt[0].s;
    return true;
    if(startk!=k&&k==1)return tt[0].f<=2;
    for(auto p:tt){
        map<int,vector<pair<pair<int,int>,pair<int,int>>>> mapa;
        for(auto d:targets){
            int dd=dist(p.s,d.f)+dist(p.s,d.s);
            mapa[dd].pb(d);
        }
        bool ok=1;
        for(auto p:mapa){
            if(!solve(p.s,k-1)){
                ok=0;
                break;
            }
        }
        if(ok){
            ans=p.s;
            return 1;
        }
        return 0;
    }
    return 0;
}
int main(){
    int t;
    if(my)t=10000;
    else
    scanf("%i",&t);
    while(t--){
        if(my){
            n=rng()%15+2;
            m=rng()%15+2;
            while(1){
                target={{rng()%n+1,rng()%m+1},{rng()%n+1,rng()%m+1}};
                if(target.f!=target.s)break;
            }
        }
        else
        scanf("%i %i",&n,&m);
        if(my)
        printf("%i %i  %i %i %i %i\n",n,m,target.f.f,target.f.s,target.s.f,target.s.s);
        int c1=scan(1,1);
        int c2=scan(1,m);
        vector<pair<pair<int,int>,pair<int,int>>> targets;
        for(int x1=1;x1<=n;x1++)for(int y1=1;y1<=m;y1++)for(int x2=1;x2<=n;x2++)for(int y2=1;y2<=m;y2++){
                pair<pair<int,int>,pair<int,int>> tr={{x1,y1},{x2,y2}};
                if(tr.f==tr.s||tr.f>tr.s)continue;
                int d1=dist(tr.f,{1,1})+dist(tr.s,{1,1});
                int d2=dist(tr.f,{1,m})+dist(tr.s,{1,m});
                if(d1==c1&&d2==c2){
                    targets.pb(tr);
                }
        }
        int k=2;
        while(sz(targets)>2){
            startk=k;
            assert(solve(targets,k));
            k--;
            int c=scan(ans.f,ans.s);
            vector<pair<pair<int,int>,pair<int,int>>> nt;
            for(auto p:targets){
                int dd=dist(ans,p.f)+dist(ans,p.s);
                if(dd==c){
                    nt.pb(p);
                }
            }
            targets=nt;
        }
        bool ok=dig(targets[0].f.f,targets[0].f.s);
        if(ok){
            bool ok2=dig(targets[0].s.f,targets[0].s.s);
            if(!ok){
                assert(dig(targets[1].s.f,targets[1].s.s));
            }
        }
        else{
            assert(dig(targets[1].f.f,targets[1].f.s));
            assert(dig(targets[1].s.f,targets[1].s.s));
        }
        if(my)
        printf("ok!\n");
    }
}
源文件, 语言: C++23

詳細信息

Test #1:

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

input:

1
2 3
3
1
1
1

output:

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

result:

ok (1 test case)

Test #2:

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

input:

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

output:

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

result:

ok (72 test cases)

Test #3:

score: 0
Accepted
time: 5ms
memory: 3808kb

input:

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

output:

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

result:

ok (100 test cases)

Test #4:

score: 0
Accepted
time: 5ms
memory: 3788kb

input:

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

output:

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

result:

ok (100 test cases)

Test #5:

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

input:

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

output:

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

result:

ok (100 test cases)

Test #6:

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

input:

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

output:

SCAN 1 1
SCAN 1 3
DIG 5 1
DIG 7 1
SCAN 1 1
SCAN 1 3
SCAN 2 1
DIG 1 2
DIG 1 3
DIG 4 2
SCAN 1 1
SCAN 1 3
DIG 3 1
DIG 5 1
SCAN 1 1
SCAN 1 3
SCAN 4 1
SCAN 1 2
DIG 4 1
DIG 5 3
SCAN 1 1
SCAN 1 3
DIG 1 3
DIG 4 3
SCAN 1 1
SCAN 1 3
SCAN 5 1
SCAN 1 2
DIG 3 1
DIG 8 3
SCAN 1 1
SCAN 1 3
DIG 15 2
DIG 15 3
SCAN 1 ...

result:

ok (100 test cases)

Test #7:

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

input:

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

output:

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

result:

ok (100 test cases)

Test #8:

score: 0
Accepted
time: 7ms
memory: 3792kb

input:

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

output:

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

result:

ok (100 test cases)

Test #9:

score: 0
Accepted
time: 16ms
memory: 3792kb

input:

100
16 16
34
38
22
16
1
1
16 16
34
24
34
22
1
1
16 16
28
22
18
28
1
1
16 16
17
27
17
11
1
1
16 16
34
30
26
30
0
1
1
16 16
29
21
19
25
1
1
16 16
36
28
24
22
0
1
1
16 16
43
15
35
1
1
16 16
36
40
26
18
0
1
1
16 16
38
36
26
22
1
1
16 16
21
27
13
15
1
1
16 16
24
32
14
20
1
1
16 16
41
31
25
25
0
1
1
16 16...

output:

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

result:

ok (100 test cases)

Test #10:

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

input:

100
16 16
17
23
17
13
1
1
16 16
25
37
11
17
0
1
1
16 16
45
33
25
23
0
1
1
16 16
44
20
28
20
0
1
1
16 16
33
41
29
19
1
1
16 16
29
21
17
19
1
1
16 16
47
37
27
1
1
16 16
18
24
12
16
0
1
1
16 16
36
38
34
20
1
1
16 16
21
33
11
17
0
1
1
16 16
31
29
27
19
0
1
1
16 16
28
52
4
28
1
1
16 16
17
29
11
17
1
1
16...

output:

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

result:

ok (100 test cases)

Test #11:

score: 0
Accepted
time: 13ms
memory: 3796kb

input:

100
16 16
29
41
15
27
0
1
1
16 16
35
35
25
25
0
1
1
16 16
14
26
10
14
0
1
1
16 16
55
29
29
27
1
1
16 16
18
36
18
18
1
1
16 16
28
20
18
26
0
1
1
16 16
26
14
8
24
1
1
16 16
27
33
25
17
0
1
1
16 16
19
21
17
15
0
1
1
16 16
37
31
29
23
0
1
1
16 16
24
16
16
22
0
1
1
16 16
33
7
29
5
1
1
16 16
25
27
17
19
1...

output:

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

result:

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

伺服器時間: 2024-11-30 07:55:04 | 開源專案