oj.uz

Submission #586707

# Submission time Handle Problem Language Result Execution time Memory
586707 2022-06-30T14:42:52 Z Do_you_copy Aliens (IOI07_aliens) C++14
100 / 100
 2 ms 208 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

using ll = long long;
using pii = pair <ll, ll>;

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

const ll Mod = 1000000007;
const ll maxN = 1e5 + 1;
ll n, x, y;
bool t;

bool ask1(ll x, ll y, ll d){
    if (x + d > n || x + d < 1) return 0;
    cout << "examine " << x + d << " " << y << endl;
    string s; cin >> s;
    return s == "true";
}

bool ask2(ll x, ll y, ll d){
    if (y + d > n || y + d < 1) return 0;
    cout << "examine " << x << " " << y + d << endl;
    string s; cin >> s;
    return s == "true";
}

void Init(){
    cin >> n >> x >> y;
    ll rx = x, currentx = x;
    for (ll i = 0; i < 32; ++i){
        currentx = x + (1 << i);
        currentx = min(n, currentx);
        cout << "examine " << currentx << " " << y << endl;
        string s; cin >> s;
        t = s == "true";
        if (!t || currentx == n) break;
        rx = currentx;
    }
    if (currentx == n && t) rx = n;
    else{
        while (rx <= currentx){
            ll m = (rx + currentx) / 2;
            cout << "examine " << m << " " << y << endl;
            string s; cin >> s;
            t = s == "true";
            if (t) rx = m + 1;
            else currentx = m - 1;
        }
        rx = currentx;
    }
    ll ry = y, currenty = y;
    for (ll i = 0; i < 32; ++i){
        currenty = y + (1 << i);
        currenty = min(n, currenty);
        cout << "examine " << x << " " << currenty << endl;
        string s; cin >> s;
        t = s == "true";
        if (!t || currenty == n) break;
        ry = currenty;
    }
    if (currenty == n && t) ry = n;
    else{
        while (ry <= currenty){
            ll m = (ry + currenty) / 2;
            cout << "examine " << x << " " << m << endl;
            string s; cin >> s;
            t = s == "true";
            if (t) ry = m + 1;
            else currenty = m - 1;
        }
        ry = currenty;
    }
    ll ly = y; currenty = y;
    for (ll i = 0; i < 32; ++i){
        currenty = y - (1 << i);
        currenty = max(1, currenty);
        cout << "examine " << x << " " << currenty << endl;
        string s; cin >> s;
        t = (s == "true");
        if (!t || currenty == 1) break;
        ly = currenty;
    }
    if (currenty == 1 && t) ly = 1;
    else{
        while (currenty <= ly){
            ll m = (ly + currenty) / 2;
            cout << "examine " << x << " " << m << endl;
            string s; cin >> s;
            t = s == "true";
            if (t) ly = m - 1;
            else currenty = m + 1;
        }
        ++ly;
    }
    ll lx = rx - (ry - ly);
    ll m = (ry - ly + 1);
    ll xm = (lx + rx) / 2;
    ll ym = (ly + ry) / 2;
    rx = xm; ly = ry = ym;
    for (ll i = 2; i >= 1; --i){
        if (ask1(xm, ym, 2 * m * i)){
            rx += 2 * m * i;
            break;
        }
    }
    for (ll i = 2; i >= 1; --i){
        if (ask2(xm, ym, 2 * m * i)){
            ry += 2 * m * i;
            break;
        }
    }
    for (ll i = 2; i >= 1; --i){
        if (ask2(xm, ym, - 2 * m * i)){
            ly -= 2 * m * i;
            break;
        }
    }
    lx = rx - (ry - ly);
    cout << "solution " << (lx + rx) / 2 << " " << (ly + ry) / 2 << endl;
}

int main(){
    if (fopen(taskname".txt", "r")){
        //freopen(taskname".txt", "r", stdin);
    }
    faster
    //freopen(taskname.inp, "r", stdin)
    //freopen(taskname.out, "w", stdout)
    Init();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 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 0 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
10.0 / 10.0

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

Subtask #10
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