oj.uz

Submission #348732

# Submission time Handle Problem Language Result Execution time Memory
348732 2021-01-15T15:38:58 Z apostoldaniel854 Aliens (IOI07_aliens) C++14
100 / 100
 3 ms 492 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

int n;
int nr_op;
bool ask (int x, int y) { /// if the grass on (x, y) is flattened
    if (x <= 0 || y <= 0 || x > n || y > n)
        return false;
    nr_op++;
    assert (nr_op <= 300);
    cout << "extract " << x << " " << y << endl;
    string answer;
    cin >> answer;
    if (answer == "true")
        return true;
    return false;
}
int dx[] = {1, 1, -1, -1};
int dy[] = {1, -1, 1, -1};
int dxS[] = {0, 0, -1, 1};
int dyS[] = {-1, 1, 0, 0};

int main() {
    int xn, yn;
    cin >> n >> xn >> yn;
    int sz = 0;
    int x = xn, y = yn;
    while (ask (x, y + (1 << sz)))
        sz++;
    sz--;
    int y2 = y;
    while (sz >= 0) {
        if (ask (x, y2 + (1 << sz)))
            y2 += (1 << sz);
        sz--;
    }
    sz = 0;
    while (ask (x, y - (1 << sz)))
        sz++;
    sz--;
    int y1 = y;
    while (sz >= 0) {
        if (ask (x, y1 - (1 << sz)))
            y1 -= (1 << sz);
        sz--;
    }

    sz = 0;
    while (ask (x + (1 << sz), y))
        sz++;
    sz--;
    int x2 = x;
    while (sz >= 0) {
        if (ask (x2 + (1 << sz), y))
            x2 += (1 << sz);
        sz--;
    }
    sz = 0;
    while (ask (x - (1 << sz), y))
        sz++;
    sz--;
    int x1 = x;
    while (sz >= 0) {
        if (ask (x1 - (1 << sz), y))
            x1 -= (1 << sz);
        sz--;
    }
    int m = x2 - x1 + 1;
    int x_mid = x1 + (x2 - x1 + 1) / 2;
    int y_mid = y1 + (y2 - y1 + 1) / 2;
//    cout << m << " " << x_mid << " " << y_mid << "\n";
    while (ask (x_mid - m, y_mid - m))
        x_mid -= m, y_mid -= m;
    while (ask (x_mid - 2 * m, y_mid))
        x_mid -= 2 * m;
    while (ask (x_mid, y_mid - 2 * m))
        y_mid -= 2 * m;
    cout << "solution " << x_mid + 2 * m << " " << y_mid + 2 * m << endl;
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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