Submission #642261

#	Time	Username	Problem	Language	Result	Execution time	Memory
642261		devariaota	Aliens (IOI07_aliens)	C++17	0 / 100	2 ms	208 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long ll;
// const ll mod = 1e9 + 7;
const ll MAXN = 1e6 + 5;
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define sc second
#define gl                        ios_base::sync_with_stdio(0);   cin.tie(0);                     cout.tie(0)

ll n, x, y;

bool ask(ll i, ll j)
{
  if (i <= 0 or i > n or j <= 0 or j > n)
    return 0;
  cout << "examine " << i << ' ' << j << endl;
  string in;
  cin >> in;
  return (in == "true");
}

int main()
{
  gl;
  cin >> n >> x >> y;

  ll kanan = 0, kiri = 0, atas = 0, bawah = 0;
  // cari kanan
  ll cur = 1;
  while (x + cur <= n and ask(x + cur, y))
    cur <<= 1;

  if (cur > 1)
  {
    kanan = cur >> 1;
    int l = kanan + 1, r = min(cur, n - x);
    while (l <= r)
    {
      int m = (l + r) / 2;
      if (m == kanan)
        continue;
      if (ask(x + m, y))
      {
        kanan = m;
        l = m + 1;
      }
      else
        r = m - 1;
    }
  }

  // cari kiri
  cur = 1;
  while (x - cur >= 1 and ask(x - cur, y))
    cur <<= 1;

  if (cur > 1)
  {
    kiri = cur >> 1;
    int l = kiri + 1, r = min(cur, x - 1);
    while (l <= r)
    {
      int m = (l + r) / 2;
      if (m == kiri)
        continue;
      if (ask(x - m, y))
      {
        kiri = m;
        l = m + 1;
      }
      r = m - 1;
    }
  }

  // cari atas
  cur = 1;
  while (y + cur <= n and ask(x, y + cur))
    cur <<= 1;

  if (cur > 1)
  {
    atas = cur >> 1;
    int l = atas + 1, r = min(cur, n - y);
    while (l <= r)
    {
      int m = (l + r) / 2;
      if (m == atas)
        continue;
      if (ask(x, y + m))
      {
        atas = m;
        l = m + 1;
      }
      else
        r = m - 1;
    }
  }
  // cari bawah
  cur = 1;
  while (y - cur >= 1 and ask(x, y - cur))
    cur <<= 1;

  if (cur > 1)
  {
    bawah = cur >> 1;
    int l = bawah + 1, r = min(cur, y - 1);
    while (l <= r)
    {
      int m = (l + r) / 2;
      if (m == bawah)
        continue;
      if (ask(x, y - m))
      {
        bawah = m;
        l = m + 1;
      }
      r = m - 1;
    }
  }

  ll m = (atas + bawah) / 2;

  if (atas > bawah)
    y += atas - m;
  else if (atas < bawah)
    y -= bawah - m;

  if (kanan > kiri)
    x -= kanan - m;
  else if (kanan < kiri)
    x += m - kiri;

  kanan = 0, kiri = 0, atas = 0, bawah = 0;

  m = m * 2 + 1;
  ll now = 2;
  while (x + now * m <= n and ask(x + now * m, y))
    now *= 2;
  kanan = (now - 2) / 2;

  now = 2;
  while (x - now * m >= 1 and ask(x - now * m, y))
    now *= 2;
  kiri = (now - 2) / 2;

  now = 2;
  while (y + now * m <= n and ask(x, y + now * m))
    now *= 2;
  atas = (now - 2) / 2;

  now = 2;
  while (y - now * m >= 1 and ask(x, y - now * m))
    now *= 2;
  bawah = (now - 2) / 2;

  if (atas > bawah)
    y += (atas - 2) * 2 * m;
  else if (atas < bawah)
    y -= (bawah - 2) * 2 * m;
  ;

  if (kanan > kiri)
    x += (kanan - 2) * 2 * m;
  else if (kanan < kiri)
    x -= (2 - kiri) * 2 * m;

  cout << "solution " << x << ' ' << y << endl;

  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