Submission #642264

#	Time	Username	Problem	Language	Result	Execution time	Memory
642264		andecaandeci	Aliens (IOI07_aliens)	C++17	100 / 100	3 ms	288 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");
}

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

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

  return ret;
}

int main(){
  cin >> n >> x >> y;
  ll kanan = x + find(1, 0), kiri = x - find(-1, 0), atas = y + find(0, 1), bawah = y - find(0, -1);
  ll m = (kanan - kiri + 1);
  ll cx = (kanan + kiri) / 2, cy = (atas + bawah) / 2;

  x = cx - m * 2LL, y = cy;
  while(ask(x, y)) x -= m * 2LL;
  kiri = x + (m * 2LL);

  x = cx + m * 2LL, y = cy;
  while(ask(x, y)) x += m * 2LL;
  kanan = x - (m * 2LL);

  x = cx, y = cy - m * 2LL;
  while(ask(x, y)) y -= m * 2LL;
  atas = y + (m * 2LL);

  x = cx, y = cy + m * 2LL;
  while(ask(x, y)) y += m * 2LL;
  bawah = y - (m * 2LL);

  ll ax = (kiri + kanan) / 2, ay = (bawah + atas) / 2;

  cout << "solution " << ax << ' ' << ay << endl;
}

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