Submission #1259660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259660		user736482	Worm Worries (BOI18_worm)	C++20	41 / 100	344 ms	436 KiB

worm

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099LL

ll p1,k1,p2,k2,p3,k3,X,Y,Z,val, mx,my,mz;
ll zap(ll x,ll y,ll z){
    if(x<1 || y<1 || z<1 || x>X || y>Y || z>Z)return -1;
    cout<<"? "<<x<<" "<<y<<" "<<z<<endl;
    ll ans;
    cin>>ans;
    return ans;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>k1>>k2>>k3>>Z;
    val=-1;
    mx=my=mz=1;
    X=k1;
    Y=k2;
    Z=k3;
    p1=1;
    p2=1;
    p3=1;
    while(p1!=k1 || p2!=k2 || p3!=k3){
        ll a1=k1-p1;
        ll a2=k2-p2;
        ll a3=k3-p3;
        ll m1=(p1+k1)/2;
        ll m2=(p2+k2)/2;
        ll m3=(p3+k3)/2;
        if(a1==max(a1,max(a2,a3))){
            //cout<<m1<<" ";
            ll x=-1,y=-1,z=-1;
            ll bst=-1;
            for(ll i=p2;i<=k2;i++){
                for(ll j=p3;j<=k3;j++){
                    ll pom=zap(m1,i,j);
                    if(pom>bst){
                        bst=pom;
                        x=m1;
                        y=i;
                        z=j;
                    }
                }
            }
            //cout<<x<<" "<<y<<" "<<z<<" ";
            
            ll ls=zap(x-1,y,z); 
            ll pw=zap(x+1,y,z);
            if(val>bst){
                if(mx<x){
                    ls=val;
                }
                else{
                    pw=val;
                }
            }
            
            if(max(ls,pw)<=bst){
                cout<<"! "<<x<<" "<<y<<" "<<z<<endl;return 0;
            }
            else{
                if(ls>=pw){
                    if(ls>val){
                        val=ls;
                        mx=x-1;
                        my=y;
                        mz=z;
                    }
                    k1=m1-1;
                }
                else{
                    if(pw>val){
                        val=pw;
                        mx=x+1;
                        my=y;
                        mz=z;
                    }
                    p1=m1+1;
                }
            }
            continue;
        }
        
        if(a2==max(a1,max(a2,a3))){
            ll x=-1,y=-1,z=-1;
            ll bst=-1;
            for(ll i=p1;i<=k1;i++){
                for(ll j=p3;j<=k3;j++){
                    ll pom=zap(i,m2,j);
                    if(pom>bst){
                        bst=pom;
                        x=i;
                        y=m2;
                        z=j;
                    }
                }
            }
            ll ls=zap(x,y-1,z); 
            ll pw=zap(x,y+1,z);
            if(val>bst){
                if(my<y){
                    ls=val;
                }
                else{
                    pw=val;
                }
            }
            if(max(ls,pw)<=bst){
                cout<<"! "<<x<<" "<<y<<" "<<z<<endl;return 0;
            }
            else{
                if(ls>=pw){
                    if(ls>val){
                        val=ls;
                        mx=x;
                        my=y-1;
                        mz=z;
                    }
                    k2=m2-1;
                }
                else{
                    if(pw>val){
                        val=pw;
                        mx=x;
                        my=y+1;
                        mz=z;
                    }
                    p2=m2+1;
                }
            }
            continue;
        }
        if(a3==max(a1,max(a2,a3))){
            ll x=-1,y=-1,z=-1;
            ll bst=-1;
            for(ll i=p2;i<=k2;i++){
                for(ll j=p1;j<=k1;j++){
                    ll pom=zap(j,i,m3);
                    if(pom>bst){
                        bst=pom;
                        x=j;
                        y=i;
                        z=m3;
                    }
                }
            }
            ll ls=zap(x,y,z-1); 
            ll pw=zap(x,y,z+1);
            if(val>bst){
                if(ls>=pw){
                    if(ls>val){
                        val=ls;
                        mx=x;
                        my=y;
                        mz=z-1;
                    }
                    k3=m3-1;
                }
                else{
                    if(pw>val){
                        val=pw;
                        mx=x;
                        my=y;
                        mz=z+1;
                    }
                    p3=m3+1;
                }
            }
            if(max(ls,pw)<=bst){
                cout<<"! "<<x<<" "<<y<<" "<<z<<endl;return 0;
            }
            else{
                if(ls>=pw){
                    k3=m3-1;
                }
                else
                    p3=m3+1;
            }
            continue;
        }
    }
    cout<<"! "<<p1<<" "<<p2<<" "<<p3<<endl;
}

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