oj.uz

Submission #119275

# Submission time Handle Problem Language Result Execution time Memory
119275 2019-06-20T20:20:50 Z eriksuenderhauf Aliens (IOI07_aliens) C++11
100 / 100
 4 ms 412 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char resp[30];
ll n, x, y;

bool qry(ll x0, ll y0) {
	if (x0 > n || y0 > n || x0 < 1 || y0 < 1)
		return false;
	printf("examine %lld %lld\n", x0, y0);
	fflush(stdout);
	scanf("%s", resp);
	return resp[0] == 't';
}

ll solveX(ll dir) {
	for (ll i = 1;; i *= 2) {
		if (qry(x + i * dir, y)) continue;
		if (i == 1) return x;
		ll lo = x + dir * i / 2, hi = x + dir * i;
		while (abs(hi - lo) > 1) {
			ll mi = (lo + hi) / 2;
			if (qry(mi, y))
				lo = mi;
			else
				hi = mi;
		}
		return lo;
	}
	return dir > 0 ? n : 1;
}

ll solveY(ll dir) {
	for (ll i = 1;; i *= 2) {
		if (qry(x, y + i * dir)) continue;
		if (i == 1) return y;
		ll lo = y + dir * i / 2, hi = y + dir * i;
		while (abs(hi - lo) > 1) {
			ll mi = (lo + hi) / 2;
			if (qry(x, mi))
				lo = mi;
			else
				hi = mi;
		}
		return lo;
	}
	return dir > 0 ? n : 1;
}

ll cnt[4];
ll dx[4] = {1, 0, -1, 0};
ll dy[4] = {0, 1, 0, -1};

int main() {
	scanf("%lld %lld %lld", &n, &x, &y);
	ll mxx = solveX(1), mix = solveX(-1);
	ll mxy = solveY(1), miy = solveY(-1);
	x = (mxx+mix) / 2;
	y = (mxy+miy) / 2;
	ll m = mxx - mix + 1;
	for (ll i = 0; i < 4; i++) {
		for (cnt[i] = 1; qry(x + 2 * m * dx[i] * cnt[i], y + 2 * m * dy[i] * cnt[i]); cnt[i]++);
		cnt[i]--;
	}
	if (cnt[0] == cnt[2] && cnt[1] == cnt[3])
		return !printf("solution %lld %lld\n", x, y);
	x = x + m * (cnt[0] * dx[0] + cnt[2] * dx[2]);
	y = y + m * (cnt[1] * dy[1] + cnt[3] * dy[3]);
	printf("solution %lld %lld\n", x, y);
    return 0;
}

Compilation message

aliens.cpp: In function 'bool qry(ll, ll)':
aliens.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", resp);
  ~~~~~^~~~~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:55: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);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 412 KB Output is correct
3 Correct 4 ms 256 KB Output is correct

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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