Submission #781177

#	Time	Username	Problem	Language	Result	Execution time	Memory
781177		raysh07	Aliens (IOI07_aliens)	C++17	80 / 100	3 ms	472 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int n, x, y, m;
int q = 0;

bool query(int x1, int y1){
	if (x1 < 1 || x1 > n || y1 < 1 || y1 > n) return false;
    cout << "examine " << x1 << " " << y1 << endl;
    q++;
    assert(q <= 300);
    string ok; cin >> ok;

    if (ok == "true") return true;
    return false;
}

bool check(int x1, int y1){
    if (!query(x1, y1)) return false;

    x1 = (x1 + x) / 2;
    y1 = (y1 + y) / 2;

    if (!query(x1, y1)) return false;

    x1 = (x1 + x) / 2;
    y1 = (y1 + y) / 2;

    if (!query(x1, y1)) return false;

    return true;
}

bool areyouok(int dx, int dy){
	int x1 = x + dx * m;
	int y1 = y + dy * m;

	return query(x1, y1);
}

void print(int l, int r, int u, int d){
	//cout << l << " " << r << " " << u << " " << d << endl;
	cout << "solution " << (l + r) / 2 << " " << (u + d) / 2 << endl;
}

void Solve()
{
    cin >> n;
    cin >> x >> y;

    int ll = 1, rl = x;
    while (ll != rl){
        int mid = (ll + rl) / 2;

        if (check(mid, y)) rl = mid;
        else ll = mid + 1;
    }

    int l = ll;

  //  cout << "FOUND OUT LEFT " << l << endl;

    ll = x, rl = n;
    while (ll != rl){
        int mid = (ll + rl + 1) / 2;

        if (check(mid, y)) ll = mid;
        else rl = mid - 1;
    }

    int r = ll;

 //   cout << "FOUND OUT RIGHT " << r << endl;

    ll = 1, rl = y;
    while (ll != rl){
        int mid = (ll + rl) / 2;

        if (check(x, mid)) rl = mid;
        else ll = mid + 1;
    }

    int u = ll;

 //   cout << "FOUND OUT UP " << u << endl;

    ll = y, rl = n;
    while (ll != rl){
        int mid = (ll + rl + 1) / 2;

        if (check(x, mid)) ll = mid;
        else rl = mid - 1;
    }

    int d = ll;

   // cout << "FOUND OUT DOWN " << d << endl;

    m = (d - u + 1);
    assert(m == (r - l + 1));

    for (int i = 0; i < 5; i++){
    	for (int j = 0; j < 5; j++){
    		if ((i + j)  % 2 == 1) continue;
    		bool good = true;

    		for (int i1 = 0; i1 < 5; i1++){
    			for (int j1 = 0; j1 < 5; j1++){
    				if ((i1 + j1) % 2 == 0){
    					good &= areyouok(i1 - i, j1 - j);
    				}
    			}
    		}

    		if (good){
    			l += m * (2 - i);
    			r += m * (2 - i);
    			u += m * (2 - j);
    			d += m * (2 - j);
    			print(l, r, u, d);
    			return;
    		}
    	}
    }
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;

   // freopen("in",  "r", stdin);
   // freopen("out", "w", stdout);

  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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