Submission #226050

#TimeUsernameProblemLanguageResultExecution timeMemory
226050MKopchevWorm Worries (BOI18_worm)C++14
59 / 100
957 ms6348 KiB
#include<bits/stdc++.h>
using namespace std;

map< pair<int, pair<int,int> >,int > seen;

int n,m,k,q;

mt19937 rng(42);

int ask(pair<int, pair<int,int> > now)
{
    if(seen.count(now))return seen[now];
    cout<<"? "<<now.first<<" "<<now.second.first<<" "<<now.second.second<<endl;

    int ret;
    cin>>ret;
    seen[now]=ret;
    return ret;
}

int x_moves[6]={1,-1,0,0,0,0};
int y_moves[6]={0,0,1,-1,0,0};
int z_moves[6]={0,0,0,0,1,-1};

int main()
{
    cin>>n>>m>>k>>q;

    pair<int, pair<int,int> > best;

    for(int i=1;i<=q/2;i++)
    {
        int x=rng()%n+1;
        int y=rng()%m+1;
        int z=rng()%k+1;

        pair<int, pair<int,int> > current={x,{y,z}};

        if(i==1)best=current;
        else if(ask(best)<ask(current))best=current;
    }

    while(1)
    {
        bool stop=1;

        int x=best.first,y=best.second.first,z=best.second.second;

        for(int i=0;i<6;i++)
        {
            int x_=x+x_moves[i];
            int y_=y+y_moves[i];
            int z_=z+z_moves[i];

            if(1<=x_&&x_<=n&&1<=y_&&y_<=m&&1<=z_&&z_<=k)
            {
                pair<int, pair<int,int> > current={x_,{y_,z_}};
                if(ask(current)>ask(best)){best=current;stop=0;}
            }
        }

        if(stop)
        {
            cout<<"! "<<best.first<<" "<<best.second.first<<" "<<best.second.second<<endl;
            return 0;
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...