oj.uz

Submission #436812

# Submission time Handle Problem Language Result Execution time Memory
436812 2021-06-25T01:38:38 Z definitelynotmee Aliens (IOI07_aliens) C++
100 / 100
 3 ms 200 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MOD = 1e9 + 7;
const int MAXN = 1e6+1;

int counter = 0;

bool check(){
    counter++;
    string s;
    cin >> s;
    if(s[0] == 't')
        return true;
    return false;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, x, y;
    cin >> n >> x >> y;
    function<ll(ll,ll)> bs1 = [&](ll ini, ll fim){
        while(ini != fim){
            ll m = (ini+fim)>>1;
            cout << "examine " << m << ' ' << y << endl;
            if(check()){
                fim = m;
            } else ini = m+1;
        }
        cout << "examine " << ((ini + x)>>1) << ' ' << y << endl;
        if(!check())
            return bs1(((ini + x)>>1), x);
        
        cout << "examine " << ((((ini + x)>>1)+x)>>1) << ' ' << y << endl;
        if(!check())
            return bs1(((((ini + x)>>1)+x)>>1), x);
        return ini;
    };

    function<ll(ll,ll)> bs2 = [&](ll ini, ll fim){
        while(ini != fim){
            ll m = (ini+fim+1)>>1;
            cout << "examine " << m << ' ' << y << endl;
            if(check()){
                ini = m;
            } else fim = m-1;
        }
        cout << "examine " << ((ini + x)>>1) << ' ' << y << endl;
        if(!check())
            return bs2(x,((ini + x)>>1));
        
        cout << "examine " << ((((ini + x)>>1)+x)>>1) << ' ' << y << endl;
        if(!check())
            return bs2(x,((((ini + x)>>1)+x)>>1));
        return ini;
    };
    function<ll(ll,ll)> bs3 = [&](ll ini, ll fim){
        while(ini != fim){
            ll m = (ini+fim)>>1;
            cout << "examine " << x << ' ' << m << endl;
            if(check()){
                fim = m;
            } else ini = m+1;
        }
        return ini;
    };
    int x1 = bs1(1,x);
    int x2 = bs2(x,n);
    const int resp = x2-x1+1;
    int y1 = bs3(max(1LL,y-resp),y);
    
    while(true){
        x1-=2*resp;
        if(x1 > 0){
            cout << "examine " << x1 << ' ' << y1 << endl;
            if(check())
                continue;
        }
        x1+=2*resp;
        break;
    }
    while(true){
        y1-=2*resp;
        if(y1 > 0){
            cout << "examine " << x1 << ' ' << y1 << endl;
            if(check())
                continue;
        }
        y1+=2*resp;
        break;
    }
    if(x1 > 1 && y1 > 1){
        cout << "examine " << x1-1 << ' ' << y1-1 << endl;
        if(check())
            x1-=resp, y1-=resp;
        
    }
    if(counter >150)
        exit(1);
    cout << "solution " << x1 + 2*resp + resp/2 << ' ' << y1 + 2*resp + resp/2 << endl;
    return 0;

}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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