oj.uz

Submission #530761

# Submission time Handle Problem Language Result Execution time Memory
530761 2022-02-26T17:10:13 Z pavement Aliens (IOI07_aliens) C++17
100 / 100
 3 ms 292 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, X, Y, M, lo, hi, rans, lans, tans, rcnt, rrig, ttop, posx, posy;

bool qry(int x, int y) {
	if (x < 1 || y < 1 || x > N || y > N) return 0;
	string ret;
	cout << "examine " << x << ' ' << y << endl;
	cin >> ret;
	return ret == "true";
}

main() {
	cin >> N >> X >> Y;
	// go right
	int k;
	for (k = 0; ; k++)
		if (!qry(X + (1 << k), Y)) break;
	// boundary is within (2^(k-1), 2^k]
	lo = (k ? (1 << (k - 1)) + 1 : 1), hi = (1 << k), rans = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (!qry(X + mid, Y)) rans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	for (k = 0; ; k++)
		if (!qry(X - (1 << k), Y)) break;
	// boundary is within (2^(k-1), 2^k]
	lo = (k ? (1 << (k - 1)) + 1 : 1), hi = (1 << k), lans = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (!qry(X - mid, Y)) lans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	
	for (k = 0; ; k++)
		if (!qry(X, Y + (1 << k))) break;
	// boundary is within (2^(k-1), 2^k]
	lo = (k ? (1 << (k - 1)) + 1 : 1), hi = (1 << k), tans = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (!qry(X, Y + mid)) tans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	
	rans--, lans--, tans--;
	M = rans + lans + 1;
	X += rans;
	Y += tans;
	
	for (int k = -4; k <= 4; k++) {
		bool tmp = qry(X + k * M, Y);
		rcnt += tmp;
		if (k > 0) rrig += tmp;
	}
	for (int k = 1; k <= 4; k++) {
		bool tmp = qry(X, Y + k * M);
		ttop += tmp;
	}
	if (rcnt == 2) {
		posx = 5 - (1 + 2 * rrig);
		posy = 5 - (1 + 2 * ttop);
	} else {
		assert(rcnt == 3);
		posx = 5 - (2 * rrig);
		posy = 5 - (2 * ttop);
	}
	X += (3 - posx) * M;
	Y += (3 - posy) * M;
	cout << "solution " << X - M / 2 << ' ' << Y - M / 2 << endl;
}

Compilation message

aliens.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main() {
      | ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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