Submission #1188804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188804		racha555	Aliens (IOI07_aliens)	C++20	30 / 100	0 ms	412 KiB

aliens

#include <bits/stdc++.h>
using namespace std;

bool ask(int x,int y){
   cout<<"examine ";
   cout<<x<<" "<<y<<" \n";
   string q;
   cin>>q;
   return q=="true";
}

int main(){
      int n,x,y;
      cin>>n>>x>>y;
      int raya=1;
      if(raya+x<=n){
         while(ask(x+raya,y)){
            raya*=2;
            if(x+raya>n){
               raya=n-x;
              
               break;
            }
         }
      }
      else{
         raya=0;
      }
      
      
      int l,mid,r;
      l=x,r=x+raya;
      int bestx=x;
      while(l<=r){
            mid=l+(r-l)/2;
            if(ask(mid,y)){
               l=mid+1;
               bestx=mid;
            }
            else{
               r=mid-1;
            }
      }
      raya=1;
      if(bestx-raya>=1){
         while(ask(bestx-raya,y)){
            raya*=2;
            if(bestx-raya<1){
               raya=bestx-1;
               break;
            }
         }
      }
      else{
         raya=0;
      }
      
      l=bestx-raya,r=bestx;
      int badx=x;
      while(l<=r){
            mid=l+(r-l)/2;
            if(!ask(mid,y)){
               l=mid+1;
               badx=mid;
            }
            else{
               r=mid-1;
            }
      }
      badx+=1;
      // cout<<badx<<" "<<bestx;
      int m=bestx-badx+1;
      int midx=bestx-(m/2);
      int besty,bady;
      l=y;
      raya=1;
      if(y+raya<=n){
         while(ask(midx,y+raya)){
            raya*=2;
            if(y+raya>n){
               raya=n-y;
   
            }
         }
      }
      else{
         raya=0;
      }
      
      l=y,r=y+raya;
       besty=y;
      while(l<=r){
         // cout<<"brr brr patapim";
            mid=l+(r-l)/2;
            if(ask(midx,mid)){
               l=mid+1;
               besty=mid;
            }
            else{
               r=mid-1;
            }
      }
      int midy=besty-m/2;
      // cout<<midx<<"--"<<midy; 
      bool still=true;
      while(still){
         still=false;
         if(midx-m>=1&&midy+m<=n){
            if(ask(midx-m,midy+m)){
               still= true;
               midx=midx-m;
               midy=midy+m;
            }
         }
        
         if(!still&&midx+m<=n&&midy+m<=n){
            if(ask(midx+m,midy+m)){
               still= true;
               midx=midx+m;
               midy=midy+m;
            }
         }
         if(!still&&midx-m>=0){
            if(ask(midx-m,midy)){
               still= true;
               midx=midx-m;
               midy=midy;
            }
         }
      }
      cout<<"solution "<<midx+2*m<<" "<<midy-2*m;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10