Submission #112783

#	Time	Username	Problem	Language	Result	Execution time	Memory
112783		IVIosab	Aliens (IOI07_aliens)	C++17	100 / 100	3 ms	412 KiB

aliens

#include <bits/stdc++.h>

using namespace std;
int n,nx,ny;
int findright(){
    int x=nx,y=ny;
    int cnt=1;
    int l=0,r=0;
    while(true){
        string in;
        if(x+cnt<=n) {
            cout << "examine " << x + cnt << " " << y << endl;
            cin >> in;
        }
        else{
            r=n;
            l=x+(cnt/2);
            break;
        }
        if(in!="true"){
            l=x+(cnt/2);
            r=x+cnt;
            break;
        }
        else {
            cnt *= 2;
        }
    }
    while (l < r) {
        int mid = l + (r - l + 1) / 2;
        cout<<"examine "<<mid<<" "<<y<<endl;
        string st;
        cin>>st;
        if (st=="true") l = mid;
        else r = mid - 1;
    }
    return l;
}
int findleft(){
    int x=nx,y=ny;
    int cnt=1;
    int l=0,r=0;
    while(true){
        string in;
        if(x-cnt>=1) {
            cout << "examine " << x - cnt << " " << y << endl;
            cin >> in;
        }
        else{
            l=1;
            r=x-(cnt/2);
            break;
        }
        if(in!="true"){
            l=x-cnt;
            r=x-(cnt/2);
            break;
        }
        else {
            cnt *= 2;
        }
    }
    while (l < r) {
        int mid = (l + (r - l) / 2);
        cout<<"examine "<<mid<<" "<<y<<endl;
        string st;
        cin>>st;
        if (st=="true") r = mid;
        else l = mid + 1;
    }
    return l;
}
int findbottom(){
    int x=nx,y=ny;
    int cnt=1;
    int l=0,r=0;
    while(true){
        string in;
        if(y-cnt>=1) {
            cout << "examine " << x << " " << y - cnt << endl;
            cin >> in;
        }
        else{
            l=1;
            r=y-(cnt/2);
            break;
        }
        if(in!="true"){
            l=y-cnt;
            r=y-(cnt/2);
            break;
        }
        else {
            cnt *= 2;
        }
    }
    while (l < r) {
        int mid = (l + (r - l) / 2);
        cout<<"examine "<<x<<" "<<mid<<endl;
        string st;
        cin>>st;
        if (st=="true") r = mid;
        else l = mid + 1;
    }
    return l;
}
int main() {
    //freopen("sample-8.in", "r", stdin);
    //freopen("output8.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>nx>>ny;
    int r=findright(),l=findleft(),b=findbottom();
    int m=r-l+1;
    int resx=l+(m/2),resy=b+(m/2);
    string sr;
    while(true){
        if(resx+m>n||resy+m>n){
            break;
        }
        cout<<"examine "<<resx+m<<" "<<resy+m<<endl;
        string st;
        cin>>st;
        if(st=="false"){
            break;
        }
        else{
            resx+=m;
            resy+=m;
        }
    }
    m*=2;
    if(resx-m>=1) {
        cout << "examine " << resx - m << " " << resy << endl;
        cin >> sr;
        if (sr == "false") {
            resx += m;
        }
    }
    else{
        resx += m;
    }
    if(resx+m<=n) {
        cout << "examine " << resx + m << " " << resy << endl;
        cin >> sr;
        if (sr == "false") {
            resx -= m;
        }
    }
    else{
        resx-=m;
    }
    if(resy-m>=1) {
        cout << "examine " << resx << " " << resy - m << endl;
        cin >> sr;
        if (sr == "false") {
            resy += m;
        }
    }
    else{
        resy+=m;
    }
    if(resy+m<=n) {
        cout << "examine " << resx << " " << resy + m << endl;
        cin >> sr;
        if (sr == "false") {
            resy -= m;
        }
    }
    else{
        resy-=m;
    }
    cout<<"solution "<<resx<<" "<<resy<<endl;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10