Submission #1259630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259630		user736482	Worm Worries (BOI18_worm)	C++20	10 / 100	342 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;
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;
    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(max(ls,pw)<=bst){
                cout<<"! "<<x<<" "<<y<<" "<<z<<endl;return 0;
            }
            else{
                if(ls>=pw){
                    k1=m1-1;
                }
                else
                    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(max(ls,pw)<=bst){
                cout<<"! "<<x<<" "<<y<<" "<<z<<endl;return 0;
            }
            else{
                if(ls>=pw){
                    k2=m2-1;
                }
                else
                    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(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: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 14
• Subtask 6: 0 / 23