Submission #951709

#	Time	Username	Problem	Language	Result	Execution time	Memory
951709		SaMuEl0516	Worm Worries (BOI18_worm)	C++17	10 / 100	3068 ms	596 KiB

worm

#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
int n,m,k;
int query(int x,int y,int z){
    if(x<1||x>n||y<1||y>m||z<1||z>k)return 0;
    if(mp.count(x+y*(n+1)+z*(n+1)*(m+1)))return mp[x+y*(n+1)+z*(n+1)*(m+1)];
    int res;
    cout<<"? "<<x<<" "<<y<<" "<<z<<endl;
    cin>>res;
    return mp[x+y*(n+1)+z*(n+1)*(m+1)]=res;
}
int main(){
    int q;
    cin>>n>>m>>k>>q;
    if(k!=1){
        
    }else if(m!=1){
        int xl=1,xr=n,yl=1,yr=m,mx=query((n+1)/2,(m+1)/2,1);
        pair<int,int>mxpos={(n+1)/2,(m+1)/2};
        while(1){
            if(query(mxpos.first,mxpos.second,1)>=query(mxpos.first,mxpos.second-1,1)
            &&query(mxpos.first,mxpos.second,1)>=query(mxpos.first,mxpos.second+1,1)){
                yl=yr=mxpos.second;
                if(query(mxpos.first,mxpos.second,1)>=query(mxpos.first-1,mxpos.second,1)
                &&query(mxpos.first,mxpos.second,1)>=query(mxpos.first+1,mxpos.second,1))break;
            }
            if(xl<xr){
                int x=(xl+xr)/2;
                if(query(x,mxpos.second,1)<mx){
                    if(x<mxpos.first)xl=x+1;
                    else xr=x-1;
                    continue;
                }else mx=query(x,mxpos.second,1),mxpos.first=x;
                if(query(x,mxpos.second,1)<query(x-1,mxpos.second,1)){
                    xr=x-1;
                    if(query(x-1,mxpos.second,1)>mx)mx=query(x-1,mxpos.second,1),mxpos.first=x-1;
                }else if(query(x,mxpos.second,1)<query(x+1,mxpos.second,1)){
                    xl=x+1;
                    if(query(x+1,mxpos.second,1)>mx)mx=query(x+1,mxpos.second,1),mxpos.first=x+1;
                }else xl=xr=x;
                if(xl==xr)yl=1,yr=m;
                continue;
            };
            int y=(yl+yr)/2;
            if(query(mxpos.first,y,1)<mx){
                if(y<mxpos.second)yl=y+1;
                else yr=y-1;
                continue;
            }else mx=query(mxpos.first,y,1),mxpos.second=y;
            if(query(mxpos.first,y,1)<query(mxpos.first,y-1,1)){
                yr=y-1;
                if(query(mxpos.first,y-1,1)>mx)mx=query(mxpos.first,y-1,1),mxpos.second=y-1;
            }else if(query(mxpos.first,y,1)<query(mxpos.first,y+1,1)){
                yl=y+1;
                if(query(mxpos.first,y+1,1)>mx)mx=query(mxpos.first,y+1,1),mxpos.second=y+1;
            }else yl=yr=y,xl=1,xr=n;
        }
        cout<<"! "<<mxpos.first<<' '<<mxpos.second<<" 1"<<endl;
    }else{
        int l=1,r=n,mx=query((n+1)/2,1,1),mxpos=(n+1)/2;
        while(l<r){
            int mid=(l+r)/2;
            if(query(mid,1,1)<mx){
                if(mid<mxpos)l=mid+1;
                else r=mid-1;
                continue;
            }else mx=query(mid,1,1),mxpos=mid;
            if(query(mid,1,1)<query(mid-1,1,1)){
                r=mid-1;
                if(query(mid-1,1,1)>mx)mx=query(mid-1,1,1),mxpos=mid-1;
            }else if(query(mid,1,1)<query(mid+1,1,1)){
                l=mid+1;
                if(query(mid+1,1,1)>mx)mx=query(mid+1,1,1),mxpos=mid+1;
            }else l=r=mid;
        }
        cout<<"! "<<l<<" 1 1"<<endl;
    }
}

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