Submission #1176548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176548		qrn	Aliens (IOI07_aliens)	C++20	0 / 100	0 ms	432 KiB

aliens

#include <bits/stdc++.h>
using namespace std;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ins insert
#define fi first
#define se second

// #define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 31;
const intt inf = 1e18;
const intt mxN = 1e6 + 5;
const intt L = 21;

bool interaction(intt x, intt y) {
    cout << "examine " << x << " " << y << endl;
    bool s;
    cin >> s;
    return s;
}
intt N, M;

bool isorta(intt x, intt y) {
    if( x - 1 >= 1 && y - 1 >= 1 && interaction(x - 1, y - 1) && 
        x - 1 >= 1 && y + 1 <= N && interaction(x - 1, y + 1) && 
        x + 1 <= N && y - 1 >= 1 && interaction(x + 1, y - 1)){
            if(x - 2 * M >= 1 && interaction(x - 2 * M, y) && x + 2 * M <= N && interaction(x+2*M, y)) {
                return false;
            }
            return true;
        }
        return false;
}

void solve() {
    intt x, y;
    cin >> N >> x >> y;
    
    intt sob = y, yb = x, sab = y, ab = x;
    
    // sol terefe
    for(intt k = 0; ; k++) {
        if(y - (1 << k) <= 0) {
            sob = 1;
            break;
        }
        if(interaction(x, y - (1 << k)) == false) {
            sob -= (1 << k);
            break;
        }
    }
    
    // yuxari terefe
    for(intt k = 0; ; k++) {
        if(x - (1 << k) <= 0) {
            yb = 1;
            break;
        }
        if(interaction(x - (1 << k), y) == false) {
            yb -= (1 << k);
            break;
        }
    }
    
    // sag terefe
    for(intt k = 0; ; k++) {
        if(y + (1 << k) > N) {
            sab = N;
            break;
        }
        if(interaction(x, y + (1 << k)) == false) {
            sab += (1 << k);
            break;
        }
    }
    
    // asagi terefe
    for(intt k = 0; ; k++) {
        if(x + (1 << k) > N) {
            ab = N;
            break;
        }
        if(interaction(x + (1 << k), y) == false) {
            ab += (1 << k);
            break;
        }
    }
    
    intt bso = 0, bsa = 0, ba = 0, by = 0;
    
    // solda
    intt l = sob, r = y;
    while(l <= r) {
        intt mid = (l + r) / 2;
        if(interaction(x, mid)) {
            bso = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    
    // sagda
    l = y, r = sab;
    while(l <= r) {
        intt mid = (l + r) / 2;
        if(interaction(x, mid)) {
            bsa = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    
    // yuxarda
    l = yb, r = x;
    while(l <= r) {
        intt mid = (l + r) / 2;
        if(interaction(mid, y)) {
            by = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    
    //asagda
    l = x, r = ab;
    while(l <= r) {
        intt mid = (l + r) / 2;
        if(interaction(mid, y)) {
            ba = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    M = ba - by + 1;
    intt acty = 0, actso = 0, actsa = 0, acta = 0;
    
    pair<intt,intt> ul = {by, bso};
    pair<intt,intt> dr = {ba, bsa};
    
    if(isorta(ul.fi, ul.se)) {
        dr.fi = ul.fi - 1;
        dr.se = ul.se - 1;
        ul.fi = ul.fi - M;
        ul.se = ul.se - M;
    }
    
    if(ul.fi - M * 4 >= 1 && interaction(ul.fi - 4 * M, y)){
        acty = ul.fi - M * 4;
    } else if(ul.fi - M * 2 >= 1 && interaction(ul.fi - 2 * M, y)) {
        acty = ul.fi - M * 2;
    } else {
        acty = ul.fi;
    }
    
    if(ul.se - M * 4 >= 1 && interaction(x, ul.se - M * 4)) {
        actso = ul.se - M * 4;
    } else if(ul.se - M * 2 >= 1 && interaction(x, ul.se - M * 2)) {
        actso = ul.se - M * 2;
    } else {
        actso = ul.se;
    }
    
    if(ul.fi + M * 4 <= N && interaction(ul.fi + 4 * M, y)){
        acta = ul.fi +  M * 4;
    } else if(ul.fi + M * 2 <= N && interaction(ul.fi + 2 * M, y)) {
        acta = ul.fi + M * 2;
    } else {
        acta = ul.fi;
    }
    
    if(ul.se + M * 4 <= N && interaction(x, ul.se + M * 4)) {
        actsa = ul.se + M * 4;
    } else if(ul.se + M * 2 <= N && interaction(x, ul.se + M * 2)) {
        actsa = ul.se + M * 2;
    } else {
        actsa = ul.se;
    }
    
    cout << "solution " << (acty + acta) / 2 + 1 << " " << (actso + actsa) / 2 + 1 << endl;
}

signed main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

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