Submission #1339290

#TimeUsernameProblemLanguageResultExecution timeMemory
1339290vyaductAliens (IOI07_aliens)C++20
80 / 100
1 ms344 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

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

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

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

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

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

void solve(){
  int n,x,y; cin>>n>>x>>y;
  if (self) fetch(n);
  int 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;
  int it_ax = last_true(0, d, [&](int 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;
  int it_ay = last_true(0, d, [&](int 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;
  int it_bx = last_true(0, d, [&](int 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;
  int it_by = last_true(0, d, [&](int j){return examine(bx, by+j);});
  by += it_by;

  int M = bx-ax+1;
  int 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...