Submission #93916

#	Time	Username	Problem	Language	Result	Execution time	Memory
93916		Diuven	Worm Worries (BOI18_worm)	C++14	0 / 100	1441 ms	9676 KiB

worm

#include <bits/stdc++.h>
using namespace std;

int n, m, k, q;
map<tuple<int, int, int>, int> mem;

int cnt=0;

void solved(int x, int y, int z){
    cout<<"! "<<x<<' '<<y<<' '<<z<<endl;
    exit(0);
}

int ask(int x, int y, int z){
    if(x<1 || n<x || y<1 || m<y || z<1 || k<z) return 0;
    int &res=mem[{x,y,z}];
    if(res>0) return res;
    static int cnt=0; cnt++;

    if(cnt>q){
        pair<tuple<int, int, int>, int> mx; mx.first={1,1,1}, mx.second=0;
        for(auto &q:mem){
            if(q.second>mx.second) mx=q;
        }
        int x,y,z; tie(x,y,z)=mx.first;
        solved(x,y,z);
    }

    cout<<"? "<<x<<' '<<y<<' '<<z<<endl;
    cin>>res;


    if(res<0) exit(0);
    return res;
}

int dx[6]={1,-1,0,0,0,0};
int dy[6]={0,0,1,-1,0,0};
int dz[6]={0,0,0,0,1,-1};

bool valid1(int x, int y, int z){
    int mx=ask(x,y,z);
    for(int k=0; k<6; k++) mx=max(mx, ask(x+dx[k], y+dy[k], z+dz[k]));
    return mx==ask(x,y,z);
}
bool valid2(int x, int y, int z){
    if(x<1 || n<x || y<1 || m<y || z<1 || k<z) return false;
    int mx=ask(x,y,z);
    for(int k=0; k<6; k++){
        int u=x+dx[k], v=y+dy[k], w=z+dz[k];
        if(mem.find({u,v,w})==mem.end()) return false;
        mx=max(mx, ask(u,v,w));
    }
    return mx==ask(x,y,z);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>k>>q;
    srand(time(NULL));
    while(true){
        int x=rand()%n+1, y=rand()%m+1, z=rand()%k+1;
        if(valid1(x,y,z)) solved(x,y,z);
        for(int k=0; k<6; k++){
            int u=x+dx[k], v=y+dy[k], w=z+dz[k];
            if(valid2(u,v,w)) solved(u,v,w);
        }
    }
    return 0;   
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 22
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 14
• Subtask 6: 0 / 23