oj.uz

Submission #642264

# Submission time Handle Problem Language Result Execution time Memory
642264 2022-09-19T06:34:50 Z andecaandeci Aliens (IOI07_aliens) C++17
100 / 100
 3 ms 288 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 288 KB Output is correct
2 Correct 3 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct