Submission #226072

#	Time	Username	Problem	Language	Result	Execution time	Memory
226072		MKopchev	Worm Worries (BOI18_worm)	C++14	81 / 100	977 ms	6408 KiB

worm

#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 ask_prep(int x,int y,int z)
{
    return ask({x,{y,z}});
}
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};

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

const double phi=(sqrt(5)+1)/2;

void solve(int l,int r,int known)
{
    //cout<<" solve "<<l<<" "<<r<<" "<<known<<endl;

    if(l==r)print(l,1,1);

    if(r-l<=5)
    {
        for(int i=l;i<=r;i++)
        {
            bool stop=1;
            for(int j=0;j<2;j++)
            {
                int x_=i+x_moves[j];

                if(1<=x_&&x_<=n)
                {
                    if(ask_prep(i,1,1)<ask_prep(x_,1,1)){stop=0;break;}
                }
            }
            if(stop)print(i,1,1);
        }
    }
    int other;

    if((l+r)/2>=known)
    {
        other=l+(r-l)/phi;
        //cout<<"other= "<<other<<endl;

        if(ask_prep(known,1,1)<ask_prep(other,1,1))solve(known,r,other);
        else solve(l,other,known);
    }
    else
    {
        other=l+(r-l)/phi/phi;
        //cout<<"other2= "<<other<<endl;

        if(ask_prep(other,1,1)<ask_prep(known,1,1))solve(other,r,known);
        else solve(l,known,other);
    }
}

void solve_1()
{
    int known=1+(n-1)/phi;

    ask_prep(known,1,1);

    solve(1,n,known);
}
int main()
{
    cin>>n>>m>>k>>q;

    if(m==1&&k==1)
    {
        solve_1();
    }

    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)
        {
            print(best.first,best.second.first,best.second.second);
        }
    }
    return 0;
}

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