제출 #222057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
222057		FieryPhoenix	Aliens (IOI07_aliens)	C++11	100 / 100	7 ms	436 KiB

aliens

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

ll N,X,Y;

bool ask(int x, int y){
  if (x<1 || x>N || y<1 || y>N) return false;
  cout<<"examine "<<x<<' '<<y<<endl;
  cout<<flush;
  string s; cin>>s;
  return s=="true";
}

ll solve(ll dirx, ll diry){
  ll len=0;
  ll i=0;
  for (;;){
    if (ask(X+len*dirx+dirx*(1<<i),Y+len*diry+diry*(1<<i))){
      len+=(1<<i);
      i++;
    }
    else break;
  }
  for (ll j=i-1;j>=0;j--){
    if (ask(X+len*dirx+dirx*(1<<j),Y+len*diry+diry*(1<<j)))
      len+=(1<<j);
  }
  return len;
}

int main()
{
  //ios_base::sync_with_stdio(0);cin.tie(0);
  //freopen (".in","r",stdin);
  //freopen (".out","w",stdout);
  cin>>N>>X>>Y;
  //cout<<"up"<<endl;
  ll up=solve(0,1);
  //cout<<"down"<<endl;
  ll down=solve(0,-1);
  //cout<<"left"<<endl;
  ll left=solve(-1,0);
  //cout<<"right"<<endl;
  ll right=solve(1,0);
  ll M=up+down+1;
  //cout<<M<<endl;
  //cout<<up<<' '<<down<<' '<<left<<' '<<right<<endl;
  assert(up+down==left+right);
  ll xc=X+right-M/2,yc=Y+up-M/2;
  //cout<<"XY: "<<xc<<' '<<yc<<endl;
  ll xmin=INF,xmax=-INF,ymin=INF,ymax=-INF;
  for (ll i=-4;i<=4;i+=2){
    if (ask(xc+M*i,yc)){
      xmin=min(xmin,xc+M*i);
      xmax=max(xmax,xc+M*i);
    }
    if (ask(xc,yc+M*i)){
      ymin=min(ymin,yc+M*i);
      ymax=max(ymax,yc+M*i);
    }
  }
  cout<<"solution "<<(xmax+xmin)/2<<' '<<(ymin+ymax)/2<<endl;
  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