Submission #226100

#	Time	Username	Problem	Language	Result	Execution time	Memory
226100		MKopchev	Worm Worries (BOI18_worm)	C++14	100 / 100	915 ms	6524 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 mx_seen=0;

int mx_x=0;
int mx_y=0;

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;

    if(mx_seen<ret)
    {
        mx_seen=ret;
        mx_x=now.first;
        mx_y=now.second.first;
    }

    seen[now]=ret;
    return ret;
}

int ask_prep(int x,int y,int z)
{
    if(x==0||x==n+1||y==0||y==m+1||z==0||z==k+1)return 0;

    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);
}

void walk(pair<int, pair<int,int> > best)
{
    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);
        }
    }
}

void test(int x,int y,int z)
{
    for(int t=0;t<6;t++)
        if(ask_prep(x,y,z)<ask_prep(x+x_moves[t],y+y_moves[t],z+z_moves[t]))return;
    print(x,y,z);
}
void solve_rect(int x1,int y1,int x2,int y2)
{
    //cout<<"solve_rect "<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;

    if(x2-x1<=2&&y2-y1<=2)
    {
        for(int x=x1;x<=x2;x++)
            for(int y=y1;y<=y2;y++)
            {
                bool stop=1;
                for(int t=0;t<4;t++)
                {
                    int x_=x+x_moves[t];
                    int y_=y+y_moves[t];

                    if(ask_prep(x,y,1)<ask_prep(x_,y_,1))
                    {
                        stop=0;
                        t=4;
                    }
                }

                if(stop)print(x,y,1);
            }
        assert(0==1);
    }
    if(x2-x1+1<=y2-y1+1)
    {
        int av=(y1+y2)/2;

        int best_x=x1;
        for(int x=x1;x<=x2;x++)
        {
            if(ask_prep(best_x,av,1)<ask_prep(x,av,1))best_x=x;
        }

        ask_prep(best_x,av-1,1);
        ask_prep(best_x,av+1,1);

        test(best_x,av,1);

        if(av+1<=mx_y)solve_rect(x1,av+1,x2,y2);

        else solve_rect(x1,y1,x2,av);
    }
    else
    {
        int av=(x1+x2)/2;

        int best_y=y1;
        for(int y=y1;y<=y2;y++)
        {
            if(ask_prep(av,best_y,1)<ask_prep(av,y,1))best_y=y;
        }

        ask_prep(av-1,best_y,1);
        ask_prep(av+1,best_y,1);

        test(av,best_y,1);

        if(av+1<=mx_x)solve_rect(av+1,y1,x2,y2);

        else solve_rect(x1,y1,av,y2);
    }
}
void solve_2()
{
    solve_rect(1,1,n,m);
}
int main()
{
    cin>>n>>m>>k>>q;

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

    if(k==1)
    {
        solve_2();
        assert(0==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;
    }

    walk(best);
    return 0;
}

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