Submission #531446

#	Time	Username	Problem	Language	Result	Execution time	Memory
531446		AdamGS	Aliens (IOI07_aliens)	C++17	100 / 100	3 ms	260 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
ll n;
bool ask(ll x, ll y) {
  if(1<=x && x<=n && 1<=y && y<=n) {
    cout << "examine " << x << " " << y << endl;
    string s;
    cin >> s;
    return s[0]=='t';
  }
  return false;
}
int main() {
  ll x, y;
  cin >> n >> x >> y;
  ll prawo=1, lewo=1, gora=1, dol=1;
  while(ask(x+prawo, y)) prawo*=2;
  while(ask(x-lewo, y)) lewo*=2;
  while(ask(x, y+gora)) gora*=2;
  while(ask(x, y-dol)) dol*=2;
  ll p=x, k=x+prawo;
  while(p<k) {
    ll sr=(p+k+1)/2;
    if(ask(sr, y)) p=sr; else k=sr-1;
  }
  prawo=p;
  p=x-lewo; k=x;
  while(p<k) {
    ll sr=(p+k)/2;
    if(ask(sr, y)) k=sr; else p=sr+1;
  }
  lewo=p;
  p=y; k=y+gora;
  while(p<k) {
    ll sr=(p+k+1)/2;
    if(ask(x, sr)) p=sr; else k=sr-1;
  }
  gora=p;
  p=y-dol; k=y;
  while(p<k) {
    ll sr=(p+k)/2;
    if(ask(x, sr)) k=sr; else p=sr+1;
  }
  dol=p;
  x=(lewo+prawo)/2;
  y=(gora+dol)/2;
  ll m=prawo-lewo+1, wx, wy;
  if(ask(x-2*m, y)) {
    if(ask(x-4*m, y)) {
      wx=x-2*m;
    } else if(ask(x+2*m, y)) {
      wx=x;
    } else {
      wx=x-m;
    }
  } else {
    if(ask(x+4*m, y)) {
      wx=x+2*m;
    } else {
      wx=x+m;
    }
  }
  if(ask(x, y-2*m)) {
    if(ask(x, y-4*m)) {
      wy=y-2*m;
    } else if(ask(x, y+2*m)) {
      wy=y;
    } else {
      wy=y-m;
    }
  } else {
    if(ask(x, y+4*m)) {
      wy=y+2*m;
    } else {
      wy=y+m;
    }
  }
  cout << "solution " << wx << " " << wy << endl;
}

• 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