Submission #964630

#	Time	Username	Problem	Language	Result	Execution time	Memory
964630		steveonalex	Aliens (IOI07_aliens)	C++17	100 / 100	1 ms	380 KiB

aliens

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int LOG_N = 31;
ll n;

int grid[20][20];

int examine(ll x, ll y){
    if (x < 1 || x > n || y < 1 || y > n) return 0;
    cout << "examine " << x << " " << y << endl;
    string verdict; cin >> verdict;
    return verdict == "true";
}

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

int binary_lift_descent(function<int(int)> f){
    if (f(1) == 0) return 0;
    int j = 0;
    for(; j < LOG_N; ++j) {
        if (f(MASK(j)) == false){
            j--;
            break;
        }
    }
    int ans = MASK(j);
    while(j--){
        if (f(ans + MASK(j))) ans += MASK(j);
    }
    return ans;
}

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

    ll x1 = 1, y1 = 1;
    cin >> n >> x1 >> y1;

    ll xL, xR, yL, yR, block_sz;
    xR = x1 + binary_lift_descent([&x1, &y1](int x){return examine(x1 + x, y1);});
    xL = x1 - binary_lift_descent([&x1, &y1](int x){return examine(x1 - x, y1);});
    block_sz = xR - xL + 1;
    yL = y1 - binary_lift_descent([&x1, &y1](int x){return examine(x1, y1 - x);});
    yR = yL + block_sz - 1;

    if (block_sz % 2 == 0) exit(-1);

    x1 = (xL + xR) / 2, y1 = (yL + yR) / 2;
    xL = xR = x1, yL = yR = y1;
    for(int i = -4; i<=4; ++i) for(int j = -4; j<=4; ++j) if ((i + j) % 2 == 0){
        if (examine(x1 + i * block_sz, y1 + j * block_sz)) {
            minimize(xL, x1 + i * block_sz);
            minimize(yL, y1 + j * block_sz);
            maximize(xR, x1 + i * block_sz);
            maximize(yR, y1 + j * block_sz);
        }
    } 

    x1 = (xL + xR) / 2, y1 = (yL + yR) / 2;
    solution(x1, y1);

    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