QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#376160 | #4575. Interactive Treasure Hunt | InfinityNS# | AC ✓ | 16ms | 4068kb | C++23 | 3.8kb | 2024-04-03 22:24:12 | 2024-04-03 22:24:12 |
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;
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");
}
}
Details
Tip: Click on the bar to expand more detailed information
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)