Submission #122123

#	Time	Username	Problem	Language	Result	Execution time	Memory
122123		tselmegkh	Aliens (IOI07_aliens)	C++14	0 / 100	3 ms	384 KiB

aliens

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

#define INF 1e9
#define MAX 100005
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define ull long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define nl '\n'
#define zai <<' '<<
#define all(a) a.begin(),a.end()
#define pc __builtin_popcount
#define debug(args...)  cerr << #args << " = "; Dbg,args; cerr << nl;
struct Dbg { template<typename T> Dbg& operator,(const T& v) { cerr << v << ", "; return *this; } } Dbg;
template <typename T> ostream& operator<<(ostream& _o_, const vector<T>& _v_){
if(!_v_.empty()){_o_<<'[';copy(_v_.begin(),_v_.end(),ostream_iterator<T>(_o_,", "));_o_<<"\b\b]";}return _o_;}
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
template<class C> void mini(C &_a, C _b) { _a = min(_a, _b); }
template<class C> void maxi(C &_a, C _b) { _a = max(_a, _b); }

ull n, x, y, rx, lx, bx, by;
bool ask(ull qx, ull qy){
    if(qx < 1 || qy < 1 || qx > n || qy > n)return false;
    cout << "examine " << qx << ' ' << qy << endl;
    string response;
    cin >> response;
    return (response == "true");
}
int main(){
    cin >> n >> x >> y;
    ull b = 1;
    ull tmpx = x,tmpy = y;
    while(ask(tmpx + b, tmpy)){
        tmpx += b;
        b = b << 1;
    }
    ull l = tmpx , r = tmpx + b;
    while(l != r){
        ull mid = (l + r + 1) >> 1;
        if(ask(mid, tmpy)){
            l = mid;
        }
        else{
            r = mid - 1;
        }
    }
    b = 1;
    rx = l;
    //cout << "baruun bulan: " << rx << endl;

    tmpx = x, tmpy = y;
    while(ask(tmpx - b, tmpy)){
        tmpx -= b;
        b = b << 1;
    }
    l = tmpx - b, r = tmpx;
    while(l != r){
        ull mid = (l + r) >> 1;
        if(ask(mid, tmpy)){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    b = 1;
    lx = r;
    //cout << "zuun bulan: " << lx << endl;
    tmpx = x, tmpy = y;
    while(ask(tmpx,tmpy - b)){
        tmpy -= b;
        b = b << 1;
    }
    l = tmpy, r = tmpy + b;
    while(l != r){
        ull mid = (l + r) >> 1;
        if(ask(tmpx, mid)){
            r = mid;
        }
        else l = mid + 1;
    }
    ull boty = r;
    //cout << "bottom bulan: " << boty << endl;
    ull m = (rx - lx) + 1;
    //cout << "m = " << m << endl;
    ull centrey = boty + (m - 1) / 2;
    ull centrex = lx + (m - 1) / 2;

    /*while(ask(centrex - 2 * m, centrey))centrex -= 2 * m;
    while(ask(centrex, centrey - 2 * m))centrey -= 2 * m;
    */
    cout << "solution " << centrex + 2 * m zai centrey + 2 * m << endl;

	return 0;
}

• 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