Submission #643864

#	Time	Username	Problem	Language	Result	Execution time	Memory
643864		KindaNameless	Aliens (IOI07_aliens)	C++14	100 / 100	3 ms	256 KiB

aliens

#include<algorithm>
#include<assert.h>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<numeric>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;

#define ll long long
#define ld long double

ll N, cnt = 0;

bool ask(ll x, ll y){
    if(x <= 0 || y <= 0 || x > N || y > N)return 0;

    cnt++;
    assert(cnt <= 300);

    cout << "examine " << x << " " << y << "\n"; cout << flush;
    string s; cin >> s;
    return s[0] == 't';
}

ll check(ll x, ll y, ll dx, ll dy){
    ll p = 1;
    while(ask(x + p*dx, y + p*dy)){
        p *= 2LL;
    }

    ll l = p/2, r = p;
    while(r - l > 1){
        ll m = (l + r) / 2;
        if(ask(x + m*dx, y + m*dy)){
            l = m;
        }
        else r = m;
    }

    return l;
}

int main(){
    //ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll x, y; cin >> N >> x >> y;

    ll L, R, D, U, a, b, c, d;
    L = x - check(x, y, -1, 0);
    R = x + check(x, y, 1, 0);
    D = y - check(x, y, 0, -1);
    U = y + check(x, y, 0, 1);

    ll M = R - L + 1;
    ll xc = (L + R)/2, yc = (D + U)/2;

    assert(M & 1);

    a = check(xc, yc, M, M);
    b = check(xc, yc, M, -M);
    c = check(xc, yc, -M, -M);
    d = check(xc, yc, -M, M);

    if(a == 4 && b == 0 && c == 0 && d == 0){xc += 2LL*M; yc += 2LL*M;}
    if(a == 2 && b == 0 && c == 0 && d == 2){xc += 0LL*M; yc += 2LL*M;}
    if(a == 0 && b == 0 && c == 0 && d == 4){xc -= 2LL*M; yc += 2LL*M;}
    if(a == 3 && b == 1 && c == 1 && d == 1){xc += 1LL*M; yc += 1LL*M;}
    if(a == 1 && b == 1 && c == 1 && d == 3){xc -= 1LL*M; yc += 1LL*M;}

    if(a == 2 && b == 2 && c == 0 && d == 0){xc += 2LL*M; yc += 0LL*M;}
    if(a == 2 && b == 2 && c == 2 && d == 2){xc += 0LL*M; yc += 0LL*M;}
    if(a == 0 && b == 0 && c == 2 && d == 2){xc -= 2LL*M; yc += 0LL*M;}

    if(a == 1 && b == 3 && c == 1 && d == 1){xc += 1LL*M; yc -= 1LL*M;}
    if(a == 1 && b == 1 && c == 3 && d == 1){xc -= 1LL*M; yc -= 1LL*M;}
    if(a == 0 && b == 4 && c == 0 && d == 0){xc += 2LL*M; yc -= 2LL*M;}
    if(a == 0 && b == 2 && c == 2 && d == 0){xc += 0LL*M; yc -= 2LL*M;}
    if(a == 0 && b == 0 && c == 4 && d == 0){xc -= 2LL*M; yc -= 2LL*M;}

    cout << "solution " << xc << " " << yc << "\n"; cout << flush;

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