Submission #586705

#	Time	Username	Problem	Language	Result	Execution time	Memory
586705		Do_you_copy	Aliens (IOI07_aliens)	C++14	80 / 100	4 ms	320 KiB

aliens

#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

using ll = long long;
using pii = pair <int, int>;

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

const ll Mod = 1000000007;
const int maxN = 1e5 + 1;
int n, x, y;
bool t;

bool ask1(int x, int y, int d){
    if (x + d > n || x + d < 1) return 0;
    cout << "examine " << x + d << " " << y << endl;
    string s; cin >> s;
    return s == "true";
}

bool ask2(int x, int y, int d){
    if (y + d > n || y + d < 1) return 0;
    cout << "examine " << x << " " << y + d << endl;
    string s; cin >> s;
    return s == "true";
}

void Init(){
    cin >> n >> x >> y;
    int rx = x, currentx = x;
    for (int i = 0; i < 32; ++i){
        currentx = x + (1 << i);
        currentx = min(n, currentx);
        cout << "examine " << currentx << " " << y << endl;
        string s; cin >> s;
        t = s == "true";
        if (!t || currentx == n) break;
        rx = currentx;
    }
    if (currentx == n && t) rx = n;
    else{
        while (rx <= currentx){
            int m = (rx + currentx) / 2;
            cout << "examine " << m << " " << y << endl;
            string s; cin >> s;
            t = s == "true";
            if (t) rx = m + 1;
            else currentx = m - 1;
        }
        rx = currentx;
    }
    int ry = y, currenty = y;
    for (int i = 0; i < 32; ++i){
        currenty = y + (1 << i);
        currenty = min(n, currenty);
        cout << "examine " << x << " " << currenty << endl;
        string s; cin >> s;
        t = s == "true";
        if (!t || currenty == n) break;
        ry = currenty;
    }
    if (currenty == n && t) ry = n;
    else{
        while (ry <= currenty){
            int m = (ry + currenty) / 2;
            cout << "examine " << x << " " << m << endl;
            string s; cin >> s;
            t = s == "true";
            if (t) ry = m + 1;
            else currenty = m - 1;
        }
        ry = currenty;
    }
    int ly = y; currenty = y;
    for (int i = 0; i < 32; ++i){
        currenty = y - (1 << i);
        currenty = max(1, currenty);
        cout << "examine " << x << " " << currenty << endl;
        string s; cin >> s;
        t = (s == "true");
        if (!t || currenty == 1) break;
        ly = currenty;
    }
    if (currenty == 1 && t) ly = 1;
    else{
        while (currenty <= ly){
            int m = (ly + currenty) / 2;
            cout << "examine " << x << " " << m << endl;
            string s; cin >> s;
            t = s == "true";
            if (t) ly = m - 1;
            else currenty = m + 1;
        }
        ++ly;
    }
    int lx = rx - (ry - ly);
    int m = (ry - ly + 1);
    int xm = (lx + rx) / 2;
    int ym = (ly + ry) / 2;
    rx = xm; ly = ry = ym;
    for (int i = 2; i >= 1; --i){
        if (ask1(xm, ym, 2 * m * i)){
            rx += 2 * m * i;
            break;
        }
    }
    for (int i = 2; i >= 1; --i){
        if (ask2(xm, ym, 2 * m * i)){
            ry += 2 * m * i;
            break;
        }
    }
    for (int i = 2; i >= 1; --i){
        if (ask2(xm, ym, - 2 * m * i)){
            ly -= 2 * m * i;
            break;
        }
    }
    lx = rx - (ry - ly);
    cout << "solution " << (lx + rx) / 2 << " " << (ly + ry) / 2 << endl;
}

int main(){
    if (fopen(taskname".txt", "r")){
        //freopen(taskname".txt", "r", stdin);
    }
    faster
    //freopen(taskname.inp, "r", stdin)
    //freopen(taskname.out, "w", stdout)
    Init();
}

• 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: 0 / 10
• Subtask 10: 0 / 10