Submission #1259791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259791		user736482	Worm Worries (BOI18_worm)	C++20	10 / 100	0 ms	432 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,a,b,c;
bool inv=0;
ll cnt=0;
ll zap(ll x,ll y,ll z){
    cnt++;
    if(x<1 || y<1 || z<1 || x>X || y>Y || z>Z)return -1;
    cout<<"? "<<x<<" "<<y<<" "<<z<<endl;
    ll ans=10000000-abs(800213-x);
    cin>>ans;
    return ans;
}
ll gt(ll a,ll b){
    ll x=b-a+1;
    return a+(ld)x*(3-sqrtl(5))/2;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>a>>b>>c>>X;
    X=a;
    Y=b;
    Z=c;
    
    ll pocz=1;
    ll kon=a;
    ll lw=-1;
    ll glw=-1;
    ll pw=-1;
    ll gpw=-1;
    while(pocz!=kon){
        if(kon-pocz<=32){
            ll m1=(pocz+kon)/2;
            ll m2=m1+1;
            if(zap(m1,1,1)>zap(m2,1,1))kon=m1;
            else pocz=m2;
            continue;
        }
       if(lw==-1 || (glw==gpw && glw-pocz>kon-gpw)){glw=gt(pocz,kon);
       lw=zap(glw,1,1);}
       if(pw==-1 || glw==gpw){gpw=pocz+kon+1-gt(pocz,kon);
       pw=zap(gpw,1,1);}
       //cout<<pocz<<" "<<glw<<" "<<gpw<<" "<<kon<<" "<<kon-gpw<<" "<<glw-pocz<<"\n";
       if(lw>pw){
        kon=gpw-1;
        pw=lw;
        gpw=glw;
        glw=-1;
        lw=-1;
       }
       else{
        pocz=glw+1;
        lw=pw;
        glw=gpw;
        gpw=-1;
        pw=-1;
       }
       if(cnt>100)break;
    }
    cout<<"! "<<pocz<<" 1 1"<<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