Submission #1251822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251822		apxo	Aliens (IOI07_aliens)	C++20	0 / 100	1 ms	324 KiB

aliens

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

#define int long long

int n, m, x, y;
int cx, cy;
int fx, sx;

#ifdef duc_debug
const int maxn = 2005;
int c[maxn][maxn];
int move_x[] = {1, -1, 0, 0};
int move_y[] = {0, 0, 1, -1};
void build() {
  vector<pair<int, int>> cents;
  cents.emplace_back(cx, cy);
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      for (int t = 1; t <= 2; ++t) {
        int u = cx + (i ? 1 : -1) * m * t;
        int v = cy + (j ? 1 : -1) * m * t;
        cents.emplace_back(u, v);
      }
    }
  }
  for (int move = 0; move < 4; ++move) {
    int u = cx + (2 * m) * move_x[move];
    int v = cy + (2 * m) * move_y[move];
    cents.emplace_back(u, v);
  }
  for (auto [u, v] : cents) {
    int tx = u - m / 2, ty = v - m / 2;
    for (int i = tx; i < tx + m; ++i) {
      for (int j = ty; j < ty + m; ++j) {
        c[i][j] = 1;
      }
    }
  }
}
#endif

string ask(int x, int y) {
  #ifndef duc_debug
  cout << "examine " << x << ' ' << y << endl;
  string s; cin >> s;
  return s;
  #else
  string rsp = (c[x][y] ? "true" : "false");
  return rsp;
  #endif
}

void answer(int x, int y) {
  cout << "solution " << x << " " << y << endl;
  #ifdef duc_debug
  if (x != cx || y != cy) {
    cout << "WRONG";
  } else {
    cout << "CORRECT";
  }
  #endif
  exit(0);
}

set<pair<int, int>> s;

void get_res(int m) {
  debug(m);
  int l = y, r = n;
  int fy = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    bool flag = 0;
    if (ask(fx, mid) == "true") {
      fy = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  int cty = fy;
  if (cty - y > m) {
    cty -= 2 * m;
  }
  cty -= m / 2;
  int ctx = fx - m / 2;
  debug(ctx, cty, y, fy);
  queue<pair<int, int>> q;
  q.push(make_pair(ctx, cty));
  s.insert(make_pair(ctx, cty));
  int mn_x = 2e9, mx_x = -1;
  int mn_y = 2e9, mx_y = -1;
  while (!q.empty()) {
    auto [ctx, cty] = q.front();
    q.pop();
    mn_x = min(mn_x, ctx);
    mn_y = min(mn_y, cty);
    debug(ctx, cty);
    for (int i = -1; i < 2; ++i) {
      for (int j = -1; j < 2; ++j) {
        if (i == 0 || j == 0) continue;
        int ccx = ctx + m * i;
        int ccy = cty + m * j;
        if (ccx < 1 || ccy < 1 || ccx > n || ccy > n || s.count(make_pair(ccx, ccy))) continue;
        if (ask(ccx, ccy) == "true") {
          q.push(make_pair(ccx, ccy));
          s.insert(make_pair(ccx, ccy));
        }
      }
    }
  }
  answer(mn_x + m * 2, mn_y + m * 2); 
}

void solve() {
  cin >> n >> m >> x >> y;
  #ifdef duc_debug
    cin >> cx >> cy;
    build();
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        cout << c[i][j];
      }
      cout << '\n';
    }
  #endif
  
  int l = x, r = n;
  fx = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    bool flag = (ask(mid, y) == "true");
    if (!flag) {
      r = mid - 1;
    } else {
      fx = mid;
      l = mid + 1;
    }
  }
  
  l = 1, r = x;
  sx = -1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    bool flag = (ask(mid, y) == "true");
    if (!flag) {
      l = mid + 1;
    } else {
      sx = mid;
      r = mid - 1;
    }
  }
  debug(fx, sx);
  if ((fx - sx + 1) % 3) {
    get_res(fx - sx + 1);
  } else {
    string check = ask(sx + m / 2, y);
    if (check == "false") {
      get_res((fx - sx + 1) / 3);
    } else {
      get_res(fx - sx + 1);
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10