Submission #584627

#	Time	Username	Problem	Language	Result	Execution time	Memory
584627		RGBB	Worm Worries (BOI18_worm)	C++14	100 / 100	813 ms	5404 KiB

worm

#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
typedef short int si;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int>pi;
typedef pair<si,si>psi;
typedef pair<ll,ll>pll;
typedef pair<double,double>pd;
typedef tuple<int,int,int>ti;
typedef tuple<ll,ll,ll>tll;
typedef tuple<double,double,double>td;
typedef complex<double>cd;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>bbst;

mt19937 g1;
int get_random_int(int a,int b){
    return uniform_int_distribution<int>(a,b)(g1);
}

ll gcd(ll a,ll b){
    if(a==0)return b;
    return gcd(b%a,a);
}

const int mod=1e9+7;

int n,m,k,q;

map<ti,int>val;

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

int cnt=0;

int input(int x,int y,int z){
    if(val.find({x,y,z})!=val.end())return val[{x,y,z}];
    cout<<"? "<<x<<" "<<y<<" "<<z<<"\n"<<flush;
    cin>>val[{x,y,z}];
    return val[{x,y,z}];
}

void output(int x,int y,int z){
    cout<<"! "<<x<<" "<<y<<" "<<z<<"\n"<<flush;
}

void case1D(){
    val[{0,1,1}]=0;
    val[{n+1,1,1}]=0;
    int l=1;
    int r=n;
    input(l,1,1);
    input(r,1,1);
    int mid=(l+r)/2;
    while(r-l>1){
        input(mid,1,1);
        if(val[{mid,1,1}]<=val[{l,1,1}])r=mid;
        else if(val[{mid,1,1}]<=val[{r,1,1}])l=mid;
        else{
            input(mid-1,1,1);
            if(val[{mid,1,1}]<=val[{mid-1,1,1}])r=mid;
            else l=mid;
        }
        mid=(l+r)/2;
        if(r-l>10)mid+=get_random_int(-(r-l)/10,(r-l)/10);
    }


    if(input(r,1,1)>input(l,1,1))output(r,1,1);
    else output(l,1,1);
    return;
}

void case2D(){
    int xl=1;
    int xr=n;
    int xm=(xl+xr)/2;
    int yl=1;
    int yr=m;
    int ym=(yl+yr)/2;
    int maxx=-1;
    int maxy=-1;
    int maxv=-1;
    while(xr>xl||yr>yl){
        int x=-1;
        int y=-1;
        int v=-1;
        if(xr-xl<yr-yl){
            for(int i=xl;i<=xr;i++){
                if(input(i,ym,1)>v){
                    v=val[{i,ym,1}];
                    x=i;
                    y=ym;
                }
            }
            if(v<maxv){
                if(maxy>y)yl=ym+1;
                else yr=ym-1;
            }
            else if(y!=m&&input(x,y+1,1)>v){
                yl=ym+1;
                maxx=x;
                maxy=y;
                maxv=v;
            }
            else if(y!=1&&input(x,y-1,1)>v){
                yr=ym-1;
                maxx=x;
                maxy=y;
                maxv=v;
            }
            else{
                output(x,y,1);
                return;
            }
        }
        else{
            for(int i=yl;i<=yr;i++){
                if(input(xm,i,1)>v){
                    v=val[{xm,i,1}];
                    x=xm;
                    y=i;
                }
            }
            if(v<maxv){
                if(maxx>x)xl=xm+1;
                else xr=xm-1;
            }
            else if(x!=n&&input(x+1,y,1)>v){
                xl=xm+1;
                maxx=x;
                maxy=y;
                maxv=v;
            }
            else if(x!=1&&input(x-1,y,1)>v){
                xr=xm-1;
                maxx=x;
                maxy=y;
                maxv=v;
            }
            else{
                output(x,y,1);
                return;
            }
        }
        xm=(xl+xr)/2;
        ym=(yl+yr)/2;
    }
    output(xl,yl,1);
}

void case3D(){
    for(int i=0;i<q/2;i++){
        int x=get_random_int(1,n);
        int y=get_random_int(1,m);
        int z=get_random_int(1,k);
        if(val.find({x,y,z})!=val.end()){
            i--;
            continue;
        }
        input(x,y,z);
    }
    ti cur={-1,-1,-1};
    int cv=-1;
    for(auto&[i,j]:val){
        if(j>cv){
            cv=j;
            cur=i;
        }
    }
    while(true){
        bool bigger=false;
        for(int i=0;i<6;i++){
            int x=get<0>(cur)+dx[i];
            int y=get<1>(cur)+dy[i];
            int z=get<2>(cur)+dz[i];
            if(x<1||x>n||y<1||y>m||z<1||z>k)continue;
            if(val.find({x,y,z})==val.end()){
                if(input(x,y,z)>cv){
                    cv=val[{x,y,z}];
                    cur={x,y,z};
                    bigger=true;
                    break;
                }
            }
        }
        if(!bigger){
            output(get<0>(cur),get<1>(cur),get<2>(cur));
            return;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m>>k>>q;
    if(m==1&&k==1)case1D();
    else if(k==1)case2D();
    else case3D();
}

Compilation message (stderr)

worm.cpp: In function 'void case3D()':
worm.cpp:173:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  173 |     for(auto&[i,j]:val){
      |              ^

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