Submission #1326000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326000		SonicML	Aliens (IOI07_aliens)	C++20	100 / 100	1 ms	400 KiB

aliens

#include <iostream>

using namespace std;

typedef long long ll;

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, -1, 0, 1};

ll borderDir[4];

struct Point{
  ll x;
  ll y;
};

int n;

bool isValid(Point pos) {
  return (1 <= pos.x && pos.x <= n && 1 <= pos.y && pos.y <= n);
}

bool examineColor(Point pos) {
  cout << "examine " << pos.x << ' ' << pos.y << endl;
  string answer;
  cin >> answer;
  if(answer == "true") {
    return true;
  }
  return false;
}

bool isInside(Point pos, Point red, Point white) {
  ll minX = min(red.x, white.x);
  ll maxX = max(red.x, white.x);
  ll minY = min(red.y, white.y);
  ll maxY = max(red.y, white.y);
  if(minX <= pos.x && pos.x <= maxX && minY <= pos.y && pos.y <= maxY) {
    return true;
  }
  return false;
}

ll computeBorder(Point start, int dir) {
  Point lastRed = start;
  Point foundWhite = {0, 0};
  ll tempLimit = n+1;
  if(dir == 0 || dir == 1) {
    tempLimit = 0;
  }  
  for(int i = 0;i <= 31 && foundWhite.x == 0;i++) {
    ll moveX = dirX[dir] * (1LL<<i);
    ll moveY = dirY[dir] * (1LL<<i);
    Point pos = {lastRed.x + moveX, lastRed.y + moveY};
    if(isValid(pos)) {
      if(examineColor(pos) == true) {
        lastRed = pos;
      } else {
        foundWhite = pos;
      }
    }else {
      if(dir == 0 || dir == 2) {
        foundWhite = {tempLimit, lastRed.y};
      }else {
        foundWhite = {lastRed.x, tempLimit};
      }
    }
  } 
  foundWhite = {foundWhite.x - dirX[dir], foundWhite.y - dirY[dir]};
  for(int i = 31;i >= 0;i--) {
    ll moveX = dirX[dir] * (1LL<<i); 
    ll moveY = dirY[dir] * (1LL<<i);
    Point pos = {lastRed.x + moveX, lastRed.y + moveY};
    if(isValid(pos) && isInside(pos, lastRed, foundWhite)) {
      if(examineColor(pos) == true) {
        lastRed = pos;
      }
    }
  }
  return abs(lastRed.x - start.x) + abs(lastRed.y - start.y);
}

int main() {

  Point start;
  cin >> n >> start.x >> start.y;
  for(int dir = 0;dir < 4;dir++) {
    borderDir[dir] = computeBorder(start, dir);
    //cerr << dir << " : " << borderDir[dir] << '\n';
  }
  ll m = borderDir[0] + 1 + borderDir[2];
  Point corner = {start.x-borderDir[0], start.y-borderDir[1]};
  Point realCorner = {0, 0};
  //cerr << corner.x << ' ' << corner.y << '\n';
  bool finish = false;
  for(ll i = 1;i <= 5 && !finish;i++) {
    for(ll j = 1;j <= 5 && !finish;j++) {
      if((i + j) % 2 == 0) {
        ll distX = (5-i)*m;
        ll distY = (5-j)*m;
        Point newCorner = {corner.x-distX, corner.y-distY};
        if(isValid(newCorner)) {
          if(examineColor(newCorner)) {
            realCorner = newCorner;
            finish = true;
          }
        }
      }
    }
  }   
  ll jumpX = 2 * m + m/2;
  ll jumpY = 2 * m + m/2;
  cout << "solution " << realCorner.x + jumpX << ' ' << realCorner.y + jumpY << endl;  
  return 0;
}

• 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