Submission #525754

#	Time	Username	Problem	Language	Result	Execution time	Memory
525754		prvocislo	Aliens (IOI07_aliens)	C++17	100 / 100	2 ms	280 KiB

aliens

#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <chrono>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <queue>
#include <bitset>
#include <cmath>
#include <cassert>
typedef long long ll;
typedef long double ld;
using namespace std;

const int logn = 31;
int n, K, cx, cy, xo, yo, qu = 0;
bool query(ll i, int num)
{
	ll x, y;
	if (num == 0) x = i, y = yo;
	if (num == 1) x = xo, y = i;
	if (x < 1 || y < 1 || x > n || y > n) return false;
	qu++;
	if (qu > 300)
	{
		cout << "solution " << 1 << " " << 1 << endl;
		exit(0);
	}
	cout << "examine " << x << " " << y << endl;
	/*int xf = cx - (5 * K) / 2, yf = cy - (5 * K) / 2;
	x -= xf, y -= yf;
	if (x < 0 || y < 0 || x >= 5 * K || y >= 5 * K) return false;
	x /= K;
	y /= K;
	if ((x + y) % 2 == 0) return true;
	return false;*/
	string s;
	cin >> s;
	return s == "true";
}
int find_last(int l, int r, int good, int num) // najdeme posledne policko, ktore ma farbu l
{
	while (l < r)
	{
		int m = ((ll)l + (ll)r + 1) / 2ll;
		if (query(m, num) == good) l = m;
		else r = m - 1;
	}
	return l;
}
int k = -1;
int find_one(int i0, int num)
{
	int lw = i0, rw = i0;
	for (int b = 0; b < logn; b++)
	{
		int i = i0 - min(1 << b, i0);
		if (lw == i0 && !query(i, num)) lw = i;
		i = i0 + min(1 << b, n + 1 - i0);
		if (rw == i0 && !query(i, num)) rw = i;
	}
	if (lw == i0) lw = 0;
	if (rw == i0) rw = n + 1;
	int lb = find_last(lw, i0, 0, num) + 1;
	int rb = k == -1 ? find_last(i0, rw, 1, num) : lb + k - 1;
	k = rb - lb + 1;
	int first = lb;
	while (query((ll)first - 2ll * k, num)) first -= 2 * k;
	int last = rb;
	while (query((ll)last + 2ll * k, num)) last += 2 * k;
	return ((ll)last + (ll)first) / 2ll;
}
int main()
{
	cin >> n; // >> K;
	cin >> xo >> yo;
	//cin >> cx >> cy;
	int xc = find_one(xo, 0);
	int yc = find_one(yo, 1);
	cout << "solution " << xc << " " << yc << endl;
	return 0;
}

Compilation message (stderr)

aliens.cpp: In function 'bool query(ll, int)':
aliens.cpp:23:8: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |  ll x, y;
      |        ^
aliens.cpp:23:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |  ll x, y;
      |     ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10