oj.uz

Submission #64767

# Submission time Handle Problem Language Result Execution time Memory
64767 2018-08-05T15:02:02 Z aome Aliens (IOI07_aliens) C++17
0 / 100
 1000 ms 524 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

int n, m;
int x, y;
int xc, yc;
int cnt;
bool a[105][105];

bool ask(int i, int j) {
	if (i < 1 || i > n || j < 1 || j > n) return 0;
	printf("examine %lld %lld\n", i, j);
	fflush(stdout);
	char rep[10]; scanf("%s", &rep); return rep[0] == 't';
	// ++cnt;
	// return a[i][j];
}

void local() {
	srand(time(0));
	n = 100;
	m = rand() % ((n - 5) / 10 + 1);
	m = m * 2 + 1;
	assert(m * 5 <= n);
	int l = 1 + 5 * m / 2;
	int r = n - 5 * m / 2;
	assert(l <= r);
	xc = rand() % (r - l + 1) + l;
	yc = rand() % (r - l + 1) + l;
	vector< pair<int, int> > cand;
	for (int i = -2; i <= 2; ++i) {
		for (int j = -2; j <= 2; ++j) {
			if (abs(i - j) % 2) continue;
			int xt = xc + i * m, yt = yc + j * m;
			for (int k = -m / 2; k <= m / 2; ++k) {
				for (int l = -m / 2; l <= m / 2; ++l) {
					a[xt + k][yt + l] = 1;
					cand.push_back({xt + k, yt + l});
				}
			}
		}
	}
	int id = rand() % (int)cand.size();
	x = cand[id].first, y = cand[id].second;
	// for (int i = 1; i <= n; ++i) {
	// 	for (int j = 1; j <= n; ++j) {
	// 		cout << a[i][j];
	// 	}
	// 	cout << '\n';
	// }
	// cout << x << ' ' << y << '\n';
}

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

signed main() {
	// local();
	scanf("%lld %lld %lld", &n, &x, &y);
	int lx, rx, ly, ry;
	for (int i = 0; i < 4; ++i) {
		int cur;
		if (i == 0) cur = x - 1;
		if (i == 1) cur = n - x;
		if (i == 2) cur = y - 1;
		if (i == 3) cur = n - y;
		while (1) {
			int l = 0, r = cur;
			while (l < r) {
				int mid = (l + r + 1) >> 1;
				if (ask(x + dx[i] * mid, y + dy[i] * mid)) l = mid; else r = mid - 1;
			}
			if (l == cur) break;
			cur = l;
		}
		if (i == 0) lx = x - cur;
		if (i == 1) rx = x + cur;
		if (i == 2) ly = y - cur;
		if (i == 3) ry = y + cur;
	}
	// cout << lx << ' ' << rx << ' ' << ly << ' ' << ry << '\n';
	int xt = (lx + rx) / 2, yt = (ly + ry) / 2;
	int plx = 0, prx = 0;
	int ply = 0, pry = 0;
	while (ask(xt + (plx - 2) * m, yt)) plx -= 2;
	while (ask(xt + (prx + 2) * m, yt)) prx += 2;
	while (ask(xt, yt + (ply - 2) * m)) ply -= 2;
	while (ask(xt, yt + (pry + 2) * m)) pry += 2;
	int xr = xt + (plx + prx) * m / 2;
	int yr = yt + (ply + pry) * m / 2;
	// assert(xr == xc && yr == yc);
	printf("solution %lld %lld\n", xr, yr);
	fflush(stdout);
	// cout << xr << ' ' << yr << '\n';
	// cout << xc << ' ' << yc << '\n';
	// cout << cnt << '\n';
}

Compilation message

aliens.cpp: In function 'bool ask(long long int, long long int)':
aliens.cpp:17:32: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[10]' [-Wformat=]
  char rep[10]; scanf("%s", &rep); return rep[0] == 't';
                            ~~~~^
aliens.cpp:17:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  char rep[10]; scanf("%s", &rep); return rep[0] == 't';
                ~~~~~^~~~~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld", &n, &x, &y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
aliens.cpp:85:35: warning: 'ry' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int xt = (lx + rx) / 2, yt = (ly + ry) / 2;
                               ~~~~^~~~~
aliens.cpp:85:35: warning: 'ly' may be used uninitialized in this function [-Wmaybe-uninitialized]
aliens.cpp:85:15: warning: 'rx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int xt = (lx + rx) / 2, yt = (ly + ry) / 2;
           ~~~~^~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1029 ms 496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 524 KB Time limit exceeded
2 Halted 0 ms 0 KB -