QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376158#4575. Interactive Treasure HuntInfinityNS#TL 1ms3804kbC++233.5kb2024-04-03 22:12:482024-04-03 22:12:49

Judging History

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

  • [2024-04-03 22:12:49]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3804kb
  • [2024-04-03 22:12:48]
  • 提交

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;
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++){
            map<int,int> cnt;
            for(auto p:targets){
                int dd=dist({x,y},p.f)+dist({x,y},p.s);
                cnt[dd]++;
            }
            int mx=0;
            for(auto p:cnt){
                mx=max(mx,p.s);
            }
            tt.pb({mx,{x,y}});
        }
    }
    sort(all(tt));
    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;
}
int main(){
    int t;
    if(my)t=1000;
    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);
        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});
                if(d1==c1){
                    targets.pb(tr);
                }
        }
        int k=3;
        while(sz(targets)>2){
            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");
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
2 3
3
1
1
1

output:

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

result:

ok (1 test case)

Test #2:

score: -100
Time Limit Exceeded

input:

72
3 3
1
1
0

output:

SCAN 1 1
DIG 1 1
DIG 1 2

result: