Submission #1154604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154604		simuyu	Aliens (IOI07_aliens)	C++20	90 / 100	1 ms	436 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pll pair<ll,ll>

ll N, x, y, maxM, minM=3;
map<pll, int> anss; // 0 is unknown (default), 1 is true, 2 is false

string s;
bool is_in(ll x, ll y) {
    if (anss[pll(x,y)]) {
        return (anss[pll(x,y)])==1;
    }

    if (x<1 || x>N || y<1 || y>N) {
        return false; // cannot go out of bounds.
    }

    cout << "examine " << x << ' ' << y << endl;
    cin >> s;
    if (s[0] == 't') {
        anss[pll(x,y)] = 1;
        return true;
    } else {
        anss[pll(x,y)] = 2;
        return false;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //
    cin >> N >> x >> y;
    maxM = N/5;
    if (maxM%2 == 0) maxM--;

    anss[pll(x, y)] = 1; // in case this saves something

    // binary search out the value of M some way
    // right edge
    ll lowR = x; // x could be the right edge
    ll highR = min(N, x+maxM*3); // this is the edge of the map / edge of possibility
    ll midR;
    //cout << "BSEARCHING HIGHR" << endl;
    while (highR-lowR > 1) {
        midR = (highR+lowR)/2;
        if (is_in(midR, y)) {
            // means that this is within something - should go to the right (assume not a at a diff square)
            lowR = midR;
        } else {
            highR = midR;
        }
    }
    // notice that in the above loop, lowR is always in. highR is in iff it's the edge i think.
    if (is_in(highR, y)) {
        swap(lowR, highR);
    }
    //cout << "DONE" << endl;

    // now, lowR is the edge for sure. just, which edge, we don't know.

    // check if it could be [block w x] [gap] [block w lowR]
    if (!is_in(x+(lowR-x)/2, y) ) {
        // that means that it was the wrong edge. repeat the binary search.
        highR = x+(lowR-x)/2;
        lowR = x;

        while (highR-lowR > 1) {
            midR = (highR+lowR)/2;
            if (is_in(midR, y)) {
                // means that this is within something - should go to the right (assume not a at a diff square)
                lowR = midR;
            } else {
                highR = midR;
            }
        }
        // notice that in the above loop, lowR is always in. highR is in iff it's the edge i think.
        if (is_in(highR, y)) {
            swap(lowR, highR);
        }

    } else if (!is_in(x+(lowR-x)/4, y)) {
        // check if it could be [block w x] [gap] [block] [gap] [block w edge]
        // it's wrong, repeat binary search.

        highR = x+(lowR-x)/4;
        lowR = x;

        while (highR-lowR > 1) {
            midR = (highR+lowR)/2;
            if (is_in(midR, y)) {
                // means that this is within something - should go to the right (assume not a at a diff square)
                lowR = midR;
            } else {
                highR = midR;
            }
        }
        // notice that in the above loop, lowR is always in. highR is in iff it's the edge i think.
        if (is_in(highR, y)) {
            swap(lowR, highR);
        }
    }

    // now, lowR must be an edge.




    // repeat all this for highL.
    // binary search out the value of M some way
    // right edge
    ll highL = x; // x could be the right edge
    ll lowL = max((ll)1, x-maxM*3); // this is the edge of the map / edge of possibility
    ll midL;
    //cout << "BSEARHCING HIGHL" << endl;
    while (highL-lowL > 1) {
        midL = (highL+lowL)/2;
        if (is_in(midL, y)) {
            // means that this is within something - should go to the left (assume not a at a diff square)
            highL = midL;
        } else {
            lowL = midL;
        }
    }
    // notice that in the above loop, highL is always in. lowL is in iff it's the edge i think.
    if (is_in(lowL, y)) {
        swap(lowL, highL);
    }
    //cout << "DONE" << endl;

    // now, highL is the edge for sure. just, which edge, we don't know.

    // check if it could be [block w lowL] [gap] [block w x]
    if (!is_in(x-(x-highL)/2, y) ) {
        // that means that it was the wrong edge. repeat the binary search.
        lowL = x-(x-lowL)/2;
        highL = x;

        while (highL-lowL > 1) {
            midL = (highL+lowL)/2;
            if (is_in(midL, y)) {
                // means that this is within something - should go to the left (assume not a at a diff square)
                highL = midL;
            } else {
                lowL = midL;
            }
        }
        // notice that in the above loop, highL is always in. lowL is in iff it's the edge i think.
        if (is_in(lowL, y)) {
            swap(lowL, highL);
        }

    } else if (!is_in(x-(x-highL)/4, y)) {
        // check if it could be [block w x] [gap] [block] [gap] [block w edge]
        // it's wrong, repeat binary search.

        lowL = x-(x-highL)/4;
        highR = x;

        while (highL-lowL > 1) {
            midL = (highL+lowL)/2;
            if (is_in(midL, y)) {
                // means that this is within something - should go to the left (assume not a at a diff square)
                highL = midL;
            } else {
                lowL = midL;
            }
        }
        // notice that in the above loop, highL is always in. lowL is in iff it's the edge i think.
        if (is_in(lowL, y)) {
            swap(lowL, highL);
        }
    }

    ll m = lowR - highL + 1;
    //cout << "M = " << m << endl; // debug
    //cout << "MAXM = " << maxM << endl;






    // now binary search a vertical edge as well, to find out where we are
    // binary search out the value of M some way
    // right edge
    ll lowV = y; // x could be the right edge
    ll highV = min(N, y+maxM*3); // this is the edge of the map / edge of possibility
    ll midV;
    //cout << "BSEARCHING HIGHR" << endl;
    while (highV-lowV > 1) {
        midV = (highV+lowV)/2;
        if (is_in(x, midV)) {
            // means that this is within something - should go to the right (assume not a at a diff square)
            lowV = midV;
        } else {
            highV = midV;
        }
    }
    // notice that in the above loop, lowV is always in. highR is in iff it's the edge i think.
    if (is_in(x, highV)) {
        swap(lowV, highV);
    }
    //cout << "DONE" << endl;

    // now, lowV is the edge for sure. just, which edge, we don't know.

    // check if it could be [block w x] [gap] [block w lowV]
    if (!is_in(x, y+(lowV-y)/2) ) {
        // that means that it was the wrong edge. repeat the binary search.
        highV = y+(lowV-y)/2;
        lowV = y;

        while (highV-lowV > 1) {
            midV = (highV+lowV)/2;
            if (is_in(x, midV)) {
                // means that this is within something - should go to the right (assume not a at a diff square)
                lowV = midV;
            } else {
                highV = midV;
            }
        }
        // notice that in the above loop, lowR is always in. highV is in iff it's the edge i think.
        if (is_in(x, highV)) {
            swap(lowV, highV);
        }

    } else if (!is_in(x, y+(lowV-y)/4)) {
        // check if it could be [block w x] [gap] [block] [gap] [block w edge]
        // it's wrong, repeat binary search.

        highV = y+(lowV-y)/4;
        lowV = y;

        while (highV-lowV > 1) {
            midV = (highV+lowV)/2;
            if (is_in(x, midV)) {
                // means that this is within something - should go to the right (assume not a at a diff square)
                lowV = midV;
            } else {
                highV = midV;
            }
        }
        // notice that in the above loop, lowV is always in. highV is in iff it's the edge i think.
        if (is_in(x, highV)) {
            swap(lowV, highV);
        }
    }

    // now, lowV must be an edge.




    // GET POINTS !!
    ll midX, midY;
    midX = (lowR + highL) / 2;
    midY = lowV - (m-1)/2;







    // now, let's try going across diagonals to get to other points.

    int num_topleft = 0;
    for (int i=1; i<10; i++) {
        if (is_in(midX-m*i, midY-m*i)) {
            num_topleft = i;
        } else {
            break;
        }
    }
    int num_bottomright = 0;
    for (int i=1; i<10; i++) {
        if (is_in(midX+m*i, midY+m*i)) {
            num_bottomright = i;
        } else {
            break;
        }
    }

    //cout << "NUM TOPLEFT " << num_topleft << "; num_bottomright " << num_bottomright << endl;

    if (num_topleft + num_bottomright != 4) {
        // it's either 4, 2 or 0.
        // if it's 2 or 0, we find the right direction by going top right vs bottom left and seeing what works
        int t = (4-num_topleft-num_bottomright)/2; // either 1 or 2
        // try going topright
        if (is_in(midX+2*m, midY-2*m)) {
            midX += t*m;
            midY -= t*m;
        } else {
            midX -= t*m;
            midY += t*m;
        }

    }




    // now, align across the other diagonal.

    int num_topright = 0;
    for (int i=1; i<10; i++) {
        if (is_in(midX+m*i, midY-m*i)) {
            num_topright = i;
        } else {
            break;
        }
    }
    int num_bottomleft = 0;
    for (int i=1; i<10; i++) {
        if (is_in(midX-m*i, midY+m*i)) {
            num_bottomleft = i;
        } else {
            break;
        }
    }

    if (num_topright + num_bottomleft != 4) {
        // it's either 4, 2 or 0.
        // if it's 2 or 0, we find the right direction by going top right vs bottom left and seeing what works
        int t = (4-num_topright-num_bottomleft)/2; // either 1 or 2
        // try going topleft
        if (is_in(midX-2*m, midY-2*m)) {
            midX -= t*m;
            midY -= t*m;
        } else {
            midX += t*m;
            midY += t*m;
        }

    }


    cout << "solution " << midX << ' ' << midY << endl;





    return 0;
}

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