oj.uz

Submission #964622

# Submission time Handle Problem Language Result Execution time Memory
964622 2024-04-17T08:24:31 Z steveonalex Aliens (IOI07_aliens) C++17
0 / 100
 2 ms 344 KB 
#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 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, y1;
    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;

    x1 = (xL + xR) / 2, y1 = (yL + yR) / 2;
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -