Submission #784082

#	Time	Username	Problem	Language	Result	Execution time	Memory
784082		canadavid1	Aliens (IOI07_aliens)	C++14	0 / 100	2 ms	208 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x),end(x)
//#define GRADING
#define binary_search(op) while(r-l>1) {int m=(r+l)/2; if (op) r = m; else l = m;}
int N,X0,Y0;

#ifdef GRADING
vector<vector<bool>> grid;
int counter=0,Xc,Yc;
void grading_init()
{
    int M;
    cin >> N >> M >> X0 >> Y0 >> Xc >> Yc;
    grid.assign(N+1,vector<bool>(N+1,false));
    assert(M%2==1);
    assert(M>=3);
    assert(Xc-2*M-M/2 >= 1);
    assert(Yc-2*M-M/2 >= 1);
    assert(Xc+2*M+M/2 <= N);
    assert(Yc+2*M+M/2 <= N);
    for(int i = -2; i <= 2; i++)
        for(int j = -2; j <= 2; j++)
            if((i+j)%2==0) 
                for(int y=-M/2; y<=M/2; y++)
                    for(int x=-M/2; x<=M/2;x++)
                        grid[i*M+y+Yc][j*M+x+Xc] = true;
    assert(grid[Y0][X0]);
        
}
void grading_end(int X,int Y)
{
    assert(X==Xc);
    assert(Y==Yc);
    cout << counter << " ok\n";
}
#endif

bool query(int x, int y)
{
    if(x <= 0 || x > N || y <= 0 || y > N) return 0;
    #ifdef GRADING
    counter++;
    return grid[y][x];
    #else
    cout << "examine " << x << " " << y << "\n" << flush;
    string out;
    cin >> out;
    return out=="true";
    #endif
}


int main()
{
    #ifdef GRADING
        grading_init();
    #else
        cin >> N >> X0 >> Y0;
    #endif
    int i = 1;
    while(query(X0-i,Y0)) i*=2;
    int l=X0-i,r=X0;
    binary_search(query(m,Y0));
    int left_border = r;

    i = 1;
    while(query(X0+i,Y0)) i*=2;
    l=X0,r=X0+i;
    binary_search(!query(m,Y0));
    int right_border = l;

    i = 1;
    while(query(X0,Y0+i)) i*=2;
    l=Y0,r=Y0+i;
    binary_search(!query(m,Y0));
    int bottom_border = l;
    
    int M = right_border - left_border + 1; // inclusive bounds
    int top_border = bottom_border - M + 1;

    Y0 = top_border + M/2;
    X0 = left_border + M/2;
    while(query(X0-M,Y0)) X0 = X0-M;
    while(query(X0,Y0-M)) Y0 = Y0-M;
    if(query(X0-M,Y0-M)) {X0-=M;Y0-=M;}
    X0+=2*M;
    Y0+=2*M;
    #ifdef GRADING
    grading_end(X0,Y0);
    #else
    cout << X0+2*M << " " << Y0 + 2*M << "\n";
    #endif
}

• 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