제출 #94022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94022		tincamatei	Aliens (IOI07_aliens)	C++14	100 / 100	4 ms	376 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

int ops;

bool examine(long long l, long long c, int n) {
  string str;
  if(l < 1 || l > n || c < 1 || c > n)
    return false;
  ++ops;
  assert(ops <= 300);
  cout << "examine " << (int)l << ' ' << (int)c << endl;
  cin >> str;
  return str == "true";
}

pair<long long, long long> getNextWhite(long long l, long long c, int dl, int dc, int n) {
  int lg = 0;
  while(examine(l + dl * (1LL << lg), c + dc * (1LL << lg), n))
    ++lg;

  long long l2 = l + dl * (1LL << lg), c2 = c + dc * (1LL << lg);
  while(llabs(c2 - c) > 1 || llabs(l2 - l) > 1) {
    long long midl, midc;
    midl = (l + l2) / 2;
    midc = (c + c2) / 2;

    if(examine(midl, midc, n)) {
      l = midl;
      c = midc;
    } else {
      l2 = midl;
      c2 = midc;
    }
  }

  return make_pair(l2, c2);
}

int main() {
  int n, m;
  long long x, y;
  long long maxx, maxy, minx, miny;
  pair<long long, long long> lW, rW, dW;

  cin >> n >> x >> y;
  lW = getNextWhite(x, y, 0, -1, n);
  rW = getNextWhite(x, y, 0,  1, n);
  dW = getNextWhite(x, y, 1,  0, n);

  m = rW.second - lW.second - 1;

  y = (lW.second + rW.second) / 2;
  x = (dW.first - m / 2 - 1);

  maxx = maxy = -(1LL << 60);
  minx = miny =   1LL << 60;

  for(int i = -4; i <= 4; ++i)
    for(int j = -4; j <= 4; ++j)
      if(examine(x + i * m, y + j * m, n)) {
        maxx = max(maxx, x + i * m);
        maxy = max(maxy, y + j * m);
        minx = min(minx, x + i * m);
        miny = min(miny, y + j * m);
      }

  cout << "solution " << (int)((minx + maxx) / 2) << ' ' << (int)((miny + maxy) / 2) << endl;
  return 0;
}
/*
                      1 1 1 1 1 1 1 1 1 1
    1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
1
2           X X X       X X X       X X X
3           X X X       X X X       X X X
4           X X X       X X X       X X X
5                 X X X       X X X
6                 X X X       X X X
7                 X X X       X X X
8           X X X       X X X       X X X
9           X X X       X X X       X X X
10          X X X       X X X       X X X
11                X X X       X X X
12                X X X       X X X
13                X X X       X X X
14          X X X       X X X       X X X
15          X X X       X X X       X X X
16          X X X       X X X       X X X
17
18
*/

• 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