QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#376158 | #4575. Interactive Treasure Hunt | InfinityNS# | TL | 1ms | 3804kb | C++23 | 3.5kb | 2024-04-03 22:12:48 | 2024-04-03 22:12:49 |
Judging History
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