oj.uz

Submission #119273

# Submission time Handle Problem Language Result Execution time Memory
119273 2019-06-20T20:19:39 Z eriksuenderhauf Aliens (IOI07_aliens) C++11
100 / 100
 4 ms 384 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
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:45: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:88: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 256 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 384 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 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 2 ms 256 KB Output is correct

Subtask #7
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
3 Correct 3 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 2 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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