제출 #1339296

#제출 시각아이디문제언어결과실행 시간메모리
1339296vyaductAliens (IOI07_aliens)C++20
100 / 100
1 ms436 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define all(c) (c).begin(), (c).end()
#define F first
#define S second

ll last_true(ll lo, ll hi, function<bool(ll)>ok){
  lo--;
  while(lo<hi){
    ll mid = lo + (hi-lo+1)/2;
    if (ok(mid)) lo = mid;
    else hi = mid-1;
  }
  return lo;
}

ll first_true(ll lo, ll hi, function<bool(ll)>ok){
  hi++;
  while(lo<hi){
    ll mid = lo + (hi-lo)/2;
    if (ok(mid)) hi = mid;
    else lo = mid+1;
  }
  return lo;
}

const ll mxN = 100;
ll grid[mxN][mxN];
bool self = false;

bool examine(ll x, ll y){
  if (self) return grid[x][y];
  cout << "examine " << x << " " << y << endl;  
  fflush(stdout);
  string res; cin>>res;
  return res == "true";
}

void fetch(ll n){
  for (ll i=1;i<=n;i++) {
    string s; cin>>s;
    for (ll j=1;j<=n;j++) {
      grid[i][j] = s[j-1] == '*';
    }
  }
}

void solve(){
  ll n,x,y; cin>>n>>x>>y;
  if (self) fetch(n);
  ll ax=x, ay=y, bx=x, by=y;
  ll d;

  // while(ax > 1 && examine(ax-1, ay)) ax--;
  d=1;
  while(ax-d > 1 && examine(ax-d, ay)) d*=2;
  ll it_ax = last_true(0, d, [&](ll j){return examine(ax-j, ay);});
  ax -= it_ax;
  // while(ay > 1 && examine(ax, ay-1)) ay--;
  d=1;
  while(ay-d > 1 && examine(ax, ay-d)) d*=2;
  ll it_ay = last_true(0, d, [&](ll j){return examine(ax, ay-j);});
  ay -= it_ay;
  // while(bx < n && examine(bx+1, by)) bx++;
  d=1;
  while(bx+d < n && examine(bx+d, by)) d*=2;
  ll it_bx = last_true(0, d, [&](ll j){return examine(bx+j, by);});
  bx += it_bx;
  // while(by < n && examine(bx, by+1)) by++;
  d=1;
  while(by+d < n && examine(bx, by+d)) d*=2;
  ll it_by = last_true(0, d, [&](ll j){return examine(bx, by+j);});
  by += it_by;

  ll M = bx-ax+1;
  ll cx = (ax+bx)/2, cy = (ay+by)/2;
  while(cx - M >= 1 && cy - M >= 1 && examine(cx-M, cy-M)) cx-=M, cy-=M;
  while(cx - 2*M >= 1 && examine(cx-2*M, cy)) cx-=2*M;
  while(cy - 2*M >= 1 && examine(cx, cy-2*M)) cy-=2*M;
  cout << "solution " << cx+2*M << " " << cy+2*M << endl;
  fflush(stdout);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...