oj.uz

답안 #222057

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
222057 2020-04-12T03:08:07 Z FieryPhoenix Aliens (IOI07_aliens) C++11
100 / 100
 7 ms 436 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 436 KB Output is correct
2 Correct 5 ms 256 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 256 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 6 ms 384 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 7 ms 384 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 7 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct