oj.uz

Submission #713307

# Submission time Handle Problem Language Result Execution time Memory
713307 2023-03-21T16:42:05 Z stanislavpolyn Aliens (IOI07_aliens) C++17
80 / 100
 3 ms 208 KB 
#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); i++)
#define rf(i, a, b) for (int i = (a); i >= (b); i--)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

using namespace std;

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umn(T& a, T b) {
    return a > b ? a = b, 1 : 0;
}
template <typename T>
bool umx(T& a, T b) {
    return a < b ? a = b, 1 : 0;
}

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

int n, x, y;
int m;

bool ask(int x, int y) {
    if (x < 1 || y < 1 || x > n || y > n) return 0;

    cout << "examine " << x << " " << y << "\n" << flush;
    string s;
    cin >> s;
    return s == "true";
}

int main() {
#ifndef LOCAL
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#else
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#endif

    cin >> n >> x >> y;

    int Y1, Y2;
    {
        int y2 = n;

        fr (i, 0, 30) {
            if (!ask(x, y + pw(i))) {
                y2 = y + pw(i);
                break;
            }
        }

        int l = y;
        int r = y2;
        while (l < r) {
            int mid = l + ((r - l + 1) >> 1);

            if (ask(x, mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        assert(ask(x, l));
        assert(!ask(x, l + 1));
        Y2 = l;
    }

    {
        int y2 = 1;

        fr (i, 0, 30) {
            if (!ask(x, y - pw(i))) {
                y2 = y - pw(i);
                break;
            }
        }

        int l = y2;
        int r = y;
        while (l < r) {
            int mid = l + ((r - l) >> 1);

            if (!ask(x, mid)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        assert(ask(x, l));
        assert(!ask(x, l - 1));
        Y1 = l;
    }


    m = Y2 - Y1 + 1;


    int X1, X2;
    {
        int x2 = n;

        fr (i, 0, 30) {
            if (!ask(x + pw(i), y)) {
                x2 = x + pw(i);
                break;
            }
        }

        int l = x;
        int r = x2;
        while (l < r) {
            int mid = l + ((r - l + 1) >> 1);

            if (ask(mid, y)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        assert(ask(l, y));
        assert(!ask(l + 1, y));
        X2 = l;
    }

    {
        int x2 = 1;

        fr (i, 0, 30) {
            if (!ask(x - pw(i), y)) {
                x2 = x - pw(i);
                break;
            }
        }

        int l = x2;
        int r = x;
        while (l < r) {
            int mid = l + ((r - l) >> 1);

            if (!ask(mid, y)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        assert(ask(l, y));
        assert(!ask(l - 1, y));
        X1 = l;
    }

    
    assert(ask(X1, y));
    assert(ask(x, Y1));
    assert(ask(X2, y));
    assert(ask(x, Y2));


    x = (X1 + X2) / 2;
    y = (Y1 + Y2) / 2;

    assert(X2 - X1 == Y2 - Y1 && m % 2);



    // assert(ask(x - m / 2, y));
    // assert(ask(x, y - m / 2));
    // assert(ask(x + m / 2, y));
    // assert(ask(x, y + m / 2));

    while (1) {
        if (ask(x - 2 * m, y)) {
            x -= 2 * m;
            continue;
        }
        if (ask(x, y - 2 * m)) {
            y -= 2 * m;
            continue;
        }
        break;
    }

    if (ask(x - m, y - m)) {
        x -= m;
        y -= m;
    }
   

    x += 2 * m;
    y += 2 * m;

    cout << "solution " << x << " " << y << "\n"; 

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Incorrect 3 ms 208 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 2 ms 208 KB Incorrect
3 Halted 0 ms 0 KB -