Submission #1154542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154542		hmm789	Aliens (IOI07_aliens)	C++20	50 / 100	1 ms	432 KiB

aliens

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define INF 1000000000000000000
#define MOD 1000000007

int n;

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

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int x0, y0, L, R, U, D;
    string s;
    cin >> n >> x0 >> y0;
    // solve in horizontal dim
    int l = 1, r = x0, m;
    while(l < r) {
        m = (l+r)/2;
        if(query(m, y0)) r = m;
        else l = m+1;
    }
    L = l;
    l = x0+1; r = n+1;
    while(l < r) {
        m = (l+r)/2;
        if(query(m, y0)) l = m+1;
        else r = m;
    }
    R = l-1;
//    cout << "L R " << L << " "  << R << endl;
    if(query((L+R)/2, y0)) {
        // check if (not) xoxox
        if(query( L-1+(R-L+1)*4/5, y0 )) { // x
            int L1 = L, R1 = R;
            if(query( L-1 + (R-L+1)*5, y0 )) R1 = L-1 + (R-L+1)*5;
            else if(query( L-1 + (R-L+1)*3, y0 )) R1 = L-1 + (R-L+1)*3;
            if(query( R+1 - (R-L+1)*5, y0 )) L1 = R+1 - (R-L+1)*5;
            else if(query( R+1 - (R-L+1)*3, y0 )) L1 = R+1 - (R-L+1)*3;
            L = L1; R = R1;
        }
    } else { // __xox__
        if(query( L-1+ (R-L+1)*5/3, y0 )) R = L-1+ (R-L+1)*5/3;
        else if(query( R+1 - (R-L+1)*5/3, y0 )) L = R+1 - (R-L+1)*5/3;
        else {
            int R1 = L-1 + (R-L+1)*4/3;
            int L1 = R+1 - (R-l+1)*4/3;
            L = L1; R = R1;
        }
    }
//    cout << "final L R " << L << " "<< R << endl;
    // solve in vertical dim
    l = 1; r = y0;
    while(l < r) {
        m = (l+r)/2;
        if(query(x0, m)) r = m;
        else l = m+1;
    }
    D = l;
    l = y0+1; r = n+1;
    while(l < r) {
        m = (l+r)/2;
        if(query(x0, m)) l = m+1;
        else r = m;
    }
    U = l-1;
//    cout << "D U " << D << " "  << U << endl;
    if(query(x0, (D+U)/2)) {
        // check if (not) xoxox
        if(query( x0, D-1+(U-D+1)*4/5 )) { // x
            int D1 = D, U1 = U;
            if(query( x0, D-1 + (U-D+1)*5 )) U1 = D-1 + (U-D+1)*5;
            else if(query( x0, D-1 + (U-D+1)*3 )) U1 = D-1 + (U-D+1)*3;
            if(query( x0, U+1 - (U-D+1)*5 )) D1 = U+1 - (U-D+1)*5;
            else if(query( x0, U+1 - (U-D+1)*3 )) D1 = U+1 - (U-D+1)*3;
            D = D1; U = U1;
        }
    } else { // __xox__
        if(query( x0, D-1+ (U-D+1)*5/3 )) U = D-1+ (U-D+1)*5/3;
        else if(query( x0, U+1 - (U-D+1)*5/3 )) D = U+1 - (U-D+1)*5/3;
        else {
            int U1 = D-1 + (U-D+1)*4/3;
            int D1 = U+1 - (U-D+1)*4/3;
            D = D1; U = U1;
        }
    }
//    cout << "final D U " << D << " "<< U << endl;
    cout << "solution " << (L+R)/2 << " " << (U+D)/2 << endl;
}

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