Submission #100697

#	Time	Username	Problem	Language	Result	Execution time	Memory
100697		muradeyn	Aliens (IOI07_aliens)	C++14	80 / 100	3 ms	424 KiB

aliens

/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
#define F first
#define S second

using namespace std;

intt n;

string s;

map< pair<intt,intt> ,intt >mp;

bool ask(intt x,intt y) {
    if (mp[{x,y}])return mp[{x,y}] == 1;
    if (x >= n || x < 1 || y >= n || y < 1)return false;
    cout<<"examine "<<x<<" "<<y<<endl;
    cin>>s;
    if (s == "true")mp[{x,y}] = 1;
    else mp[{x,y}] = 2;
    return (s == "true");
}

bool pos(intt x,intt y) {
    if (x >= n || x < 1 || y >= n || y < 1)return false;
    return true;
}

intt x , y , old , rgx , lfx , m , pw , dwy , upy;

int main()
{
    FAST_READ;
    cin>>n>>x>>y;
    //Right most
    old = x; rgx = x; pw = 1;
    while (ask(x + pw , y)) {
        old = x + pw;
        pw *= 2;
    }
    intt l = old , r = x + pw;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (ask(mid , y)) {
            rgx = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    old = x; lfx = x; pw = 1;
    while (ask(x - pw , y)) {
        old = x - pw;
        pw *= 2;
    }
    l = x - pw; r = old;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (ask(mid , y)) {
            r = mid - 1;
            lfx = mid;
        }
        else l = mid + 1;
    }
    m = rgx - lfx + 1;
    old = y; dwy = y; pw = 1;
    while (ask(x,y + pw)) {
        old = y + pw;
        pw *= 2;
    }
    l = old; r = y + pw;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (ask(x,mid)) {
            l = mid + 1;
            dwy = mid;
        }
        else r = mid - 1;
    }
    upy = dwy - m + 1;
    //cout<<lfx<<" "<<rgx<<endl;
    //cout<<upy<<" "<<dwy<<endl;
    //cout<<m<<endl;
    x = lfx + (rgx - lfx) / 2;
    y = upy + (dwy - upy) / 2;
    if (ask(x + 4 * m,y)) x += 2 * m;
    else if (!(ask(x + 2 * m,y) && ask(x - 2 * m,y))) {
        if (ask(x - 4 * m,y))x -= 2 * m;
        else if (ask(x + 2 * m,y)) x += m , y += m;
        else x -= m , y += m;
    }
    if (ask(x,y + 4 * m)) y += 2 * m;
    else if (!(ask(x,y + 2 * m) && ask(x , y - 2 * m))) {
        if (ask(x,y - 4 * m))y -= 2 * m;
        else if (ask(x,y + 2 * m)) x += m , y += m;
        else x += m , y -= m;
    }
    cout<<"solution "<<x<<" "<<y<<endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 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