Submission #970540

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
970540	2024-04-26T16:56:24 Z	espnINF	Aliens (IOI07_aliens)	C++17	Compilation error	0 ms	0 KB

aliens

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// template thingy
#ifdef __cplusplus
extern "C" {
#endif
int examine(int X, int Y);
void solution(int XC, int YC);
void findCenter(ll N, ll X0, ll Y0);
#ifdef __cplusplus
}
#endif

bool deb = 0; // toggle debug mode, **CHANGE**
ll m, n, x, y, a, b, c, d, l, r, mid, p, q, up, down, le, ri, length;
ll binsearch1(ll l, ll r, bool f) { // right or up, f = 1 --> y
  while (l <= r) {
    if (l == r) break;
    else if (l == r - 1) {
      if (deb) cout << (f == 0 ? r : x) << ' ' << (f == 0 ? y : r) << '\n';
      if (examine((f == 0 ? r : x), (f == 0 ? y : r))) l = r;
      else r = l;
      break;
    }else {
      mid = (l + r) / 2;
      if (!examine((f == 0 ? mid : x), (f == 0 ? y : mid))) r = mid;
      else l = mid;
    }
  }
  return l;
}
ll binsearch2(ll l, ll r, bool f) { // left or down
  while (l <= r) {
    if (l == r) break;
    else if (l == r - 1) {
      if (deb) cout << (f == 0 ? l : x) << ' ' << (f == 0 ? y : l) << '\n';
      if (examine((f == 0 ? l : x), (f == 0 ? y : l))) r = l;
      else l = r;
      break;
    }else {
      mid = (l + r) / 2;
      if (!examine((f == 0 ? mid : x), (f == 0 ? y : mid))) l = mid;
      else r = mid;
    }
  }
  return l;
}
#define so solution
void findCenter(ll N, ll X0, ll Y0) {
  up = 0, down = 0, le = 0, ri = 0;
  x = X0; y = Y0; n = N;
  bool t = 1;
  if (deb) cout << "#1\n";
  for (int i = 1; x <= n; i *= 2) {
    x += i;
    if (x - i == n) break;
    if (x > n) x=n;
    if (!examine(x, y)) {
      c = binsearch1(x - i, x, 0);
      t = 0;
      break;
    }
  }
  if (t) c = n;
  t = 1;
  x = X0;
  if (deb) cout << "#2\n";
  for (int i = 1; y <= n; i *= 2) {
    y += i;
    if (y - i == n) break;
    if (y > n) y=n;
    if (!examine(x, y)) {
      d = binsearch1(y - i, y, 1);
      t = 0;
      break;
    }
  }
  if (t) d = n;
  t = 1;
  y = Y0;
  if (deb) cout << "#3\n";
  for (int i = 1; x >= 1; i *= 2) {
    x -= i;
    if (x + i == 1) break;
    if (x < 1) x=1;
    if (!examine(x, y)) {
      if (deb) cout << x << ' ' << x + i << '\n';
      a = binsearch2(x, x + i, 0);
      t = 0;
      break;
    }
  }
  if (t) a = 1;
  t = 1;
  x = X0;
  b = d - (c - a);
  length = c - a + 1;
  if (deb) {
    cout << a << ' ' << b << ' ' << c << ' ' << d << '\n'; 
    cout << length << "\n";
  }
  // for (int i = 1; y >= 1; i *= 2) {
  //   y -= i;
  //   if (!examine(x, y)) {
  //     b = binsearch2(y, y + i, 1);
  //     t = 0;
  //     break;
  //   }
  // }
  // if (t) b = 1;
  // t = 1;
  // y = Y0;
  p = (a + c) / 2;
  q = (b + d) / 2;
  if (deb) cout << p << ' ' << q << "\n";
  // left
  if (x - 2 * length >= 1) le += examine(x - 2 * length, y);
  if (x - 4 * length >= 1) le += examine(x - 4 * length, y);
  // right (not necessary)
  if (x + 2 * length <= n and deb) ri += examine(x + 2 * length, y);
  if (x + 4 * length <= n and deb) ri += examine(x + 4 * length, y);
  // up
  if (y + 2 * length <= n) up += examine(x, y + 2 * length);
  if (y + 4 * length <= n) up += examine(x, y + 4 * length);
  // down
  if (y - 2 * length >= 1) down += examine(x, y - 2 * length);
  if (y - 4 * length >= 1) down += examine(x, y - 4 * length);

  if (deb) cout << up << ' ' << down << ' ' << le << ' ' << ri << "\n";
  // 13 cases
  if (up == 0) {
    if (down == 2) {
      if (le == 0) so(p + 2 * length, q - 2 * length);
      else if (le == 1) so(p, q - 2 * length);
      else so(p - 2 * length, q - 2 * length);
    }else {
      if (le == 0) so(p + length, q - length);
      else so(p - length, q - length);
    }
  }else if (up == 1) {
    if (down == 1) {
      if (le == 0) so(p + 2 * length, q);
      else if (le == 1) so(p, q);
      else so(p - 2 * length, q);
    }else {
      if (le == 0) so(p + length, q + length);
      else so(p - length, q + length);
    }
  }else {
    if (le == 0) so(p + 2 * length, q + 2 * length);
    else if (le == 1) so(p, q + 2 * length);
    else so(p - 2 * length, q + 2 * length);
  }
  return;
}
// binsearch so annoying

Compilation message

/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x24): undefined reference to `main'
/usr/bin/ld: /tmp/cc4dGDKJ.o: in function `binsearch1(long long, long long, bool)':
aliens.cpp:(.text+0x49): undefined reference to `examine'
/usr/bin/ld: aliens.cpp:(.text+0x8b): undefined reference to `examine'
/usr/bin/ld: aliens.cpp:(.text+0x132): undefined reference to `examine'
/usr/bin/ld: /tmp/cc4dGDKJ.o: in function `binsearch2(long long, long long, bool)':
aliens.cpp:(.text+0x1d9): undefined reference to `examine'
/usr/bin/ld: aliens.cpp:(.text+0x21b): undefined reference to `examine'
/usr/bin/ld: /tmp/cc4dGDKJ.o:aliens.cpp:(.text+0x2c2): more undefined references to `examine' follow
/usr/bin/ld: /tmp/cc4dGDKJ.o: in function `findCenter':
aliens.cpp:(.text+0x722): undefined reference to `solution'
/usr/bin/ld: aliens.cpp:(.text+0x839): undefined reference to `solution'
collect2: error: ld returned 1 exit status