Submission #577086

#	Time	Username	Problem	Language	Result	Execution time	Memory
577086		tranxuanbach	Aliens (IOI07_aliens)	C++17	100 / 100	4 ms	344 KiB

aliens

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long
// #define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;

int n;

map <pii, bool> mppquery;

bool query(int x, int y){
    if (mppquery.count(make_pair(x, y))){
        return mppquery[make_pair(x, y)];
    }
    if (1 <= x and x <= n and 1 <= y and y <= n){
        cout << "examine " << x << ' ' << y << endl;
        string s; cin >> s;
        if (s == "true"){
            return (mppquery[make_pair(x, y)] = 1);
        }
        else{
            return (mppquery[make_pair(x, y)] = 0);
        }
    }
    else{
        return 0;
    }
}

void answer(int x, int y){
    cout << "solution " << x << ' ' << y << endl;
    exit(0);
}

int sx, sy;

int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};

int dist[4];
int m;

bool large[9][9];
int ansx, ansy;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n >> sx >> sy;

    For(d, 0, 4){
        int l = 0, r = 1;
        while (query(sx + dx[d] * r, sy + dy[d] * r)){
            r = r * 2 + 1;
        }
        r--;
        while (l < r){
            int mid = (l + r + 1) >> 1;
            if (query(sx + dx[d] * mid, sy + dy[d] * mid)){
                l = mid;
            }
            else{
                r = mid - 1;
            }
        }
        dist[d] = l;
    }
    m = dist[0] + dist[3] + 1;

    sx = ((sx - dist[0]) + (sx + dist[3])) / 2;
    sy = ((sy - dist[1]) + (sy + dist[2])) / 2;
    For(x, 0, 9){
        For(y, 0, 9){
            if (((x - 4) + (y - 4)) % 2 != 0){
                continue;
            }
            large[x][y] = query(sx + (x - 4) * m, sy + (y - 4) * m);
        }
    }
    For(x, 0, 9){
        For(y, 0, 9){
            if (((x - 4) + (y - 4)) % 2 != 0){
                continue;
            }
            bool ans = 1;
            ForE(dx, -2, 2){
                ForE(dy, -2, 2){
                    if ((dx + dy) % 2 != 0){
                        continue;
                    }
                    if (x + dx < 0 or x + dx >= 9 or y + dy < 0 or y + dy >= 9){
                        ans = 0;
                        break;
                    }
                    ans &= large[x + dx][y + dy];
                }
            }
            if (ans){
                answer(sx + (x - 4) * m, sy + (y - 4) * m);
            }
        }
    }
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

• 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