oj.uz

Submission #94022

# Submission time Handle Problem Language Result Execution time Memory
94022 2019-01-14T17:09:15 Z tincamatei Aliens (IOI07_aliens) C++14
100 / 100
 4 ms 376 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 296 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 248 KB Output is correct