oj.uz

Submission #642263

# Submission time Handle Problem Language Result Execution time Memory
642263 2022-09-19T06:10:37 Z christinelynn Aliens (IOI07_aliens) C++17
0 / 100
 1 ms 336 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long ll;
#define int 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;

void jawab(ll i, ll j)
{
  cout << "solution " << i << ' ' << j << endl;
  return;
}

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");
}

ll find(ll i, ll j)
{
  ll tmp = 1;
  while (ask(x + i * tmp, y + j * tmp))
    tmp *= 2LL;

  ll l = (tmp >> 1LL), r = tmp, ret = l;
  while (l <= r)
  {
    ll m = (l + r) / 2;
    if (ask(x + m, y))
    {
      ret = m;
      l = m + 1;
    }
    else
      r = m - 1;
  }

  return ret;
}

signed 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 *= 2LL;

  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 *= 2LL;

  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 *= 2LL;

  if (cur > 1)
  {
    atas = (cur >> 1);
    ll l = atas + 1, r = min(cur, n - y);
    while (l <= r)
    {
      ll 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 *= 2LL;

  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 *= 2LL;
  kanan = (now - 2) / 2;

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

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

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

  if (atas + bawah == 2 and kanan + kiri == 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;
  }
  else
  {
    if (kanan == 1)
      x += m;
    if (kiri == 1)
      x -= m;
    if (atas == 1)
      y += m;
    if (bawah == 1)
      y -= m;
  }

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

  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -