Submission #987288

#	Time	Username	Problem	Language	Result	Execution time	Memory
987288		huutuan	Aliens (IOI07_aliens)	C++14	100 / 100	2 ms	504 KiB

aliens

#include<bits/stdc++.h>

using namespace std;

#define int long long

int n;

bool check(int x, int y){
   if (x<1 || y<1 || x>n || y>n) return 0;
   cout << "examine " << x << ' ' << y << endl;
   string s; cin >> s;
   return s[0]=='t';
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int x0, y0;
   cin >> n >> x0 >> y0;
   int lx, rx;
   {
      int l=x0, r=2e9;
      while (l<=r){
         int mid=(l+r)>>1;
         if (check(mid, y0) && check((x0+mid)>>1, y0) && check((x0+((x0+mid)>>1))>>1, y0)) l=mid+1;
         else r=mid-1;
      }
      rx=r;
   }
   {
      int l=0, r=x0;
      while (l<=r){
         int mid=(l+r)>>1;
         if (check(mid, y0) && check((x0+mid)>>1, y0) && check((x0+((x0+mid)>>1))>>1, y0)) r=mid-1;
         else l=mid+1;
      }
      lx=l;
   }
   int m=rx-lx+1;
   int mx=(lx+rx)>>1;
   int ly, ry;
   {
      int l=y0, r=y0+m;
      while (l<=r){
         int mid=(l+r)>>1;
         if (check(x0, mid)) l=mid+1;
         else r=mid-1;
      }
      ry=r;
   }
   ly=ry-m+1;
   int my=(ly+ry)>>1;
   for (int i=-2; i<=2; ++i) for (int j=-2; j<=2; ++j) if ((i+j)%2==0){
      int tx=mx+m*i, ty=my+m*j;
      bool ans=1;
      for (int k=-2; k<=2; ++k) for (int l=-2; l<=2; ++l) if ((k+l)%2==0) ans&=check(tx+k*m, ty+l*m);
      if (ans){
         cout << "solution " << tx << ' ' << ty << endl;
         return 0;
      }
   }
   assert(false);
   return 0;
}

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