제출 #1331493

#제출 시각아이디문제언어결과실행 시간메모리
1331493hauserlAliens (IOI07_aliens)C++20
100 / 100
1 ms412 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;


ll midpoint(ll l, ll r) {
    if (l > r) swap(l, r);
    return l + (r-l) / 2;
}



bool examine(ll x, ll y) {
    
    printf("examine %lld %lld\n", x, y);
    fflush(stdout);
    string s; cin >> s;

    return s == "true";
}

ll binSearchBorderX(ll l, ll r, ll y0, bool searchLeft) {
    while (l + 1 < r) {
        ll mid = midpoint(l, r);

        if (examine(mid, y0)) {
            if (searchLeft) r = mid;
            else l = mid;
        } else {
            if (searchLeft) l = mid;
            else r = mid;
        }
    }
    return searchLeft ? r : l;
}

ll binSearchBorderY(ll t, ll b, ll x0) { // always search top
    while (t + 1 < b) {
        ll mid = midpoint(t, b);

        if (examine(x0, mid)) {
            b = mid;
        } else {
            t = mid;
        }
    }
    return b;
}

int main() {

    // find right border with exponential search

    // von links und von rechts

    // 1 indexed

    ll N,x0, y0; scanf("%lld %lld %lld", &N, &x0,&y0);

    ll left = 1;
    ll right = N;

    // find left with exponential search -> end when false or when <= 0 -> is 1 true or false -> when true then 


    ll l = x0;
    bool inSquare = true;
    ll expAdd = 1;
    
    while (inSquare) {
        
        l -= expAdd;
        if (l <= 0) {
            l += expAdd;
            break;
        }

        inSquare = examine(l, y0);
        expAdd <<= 1;
    }

    if (inSquare) {
        inSquare = examine(1, y0);

        if (inSquare) {
            left = 1;
        } else {
            left = binSearchBorderX(1, l, y0, true);
        }
    } else {
        expAdd >>= 1;
        left = binSearchBorderX(l, l+expAdd, y0, true);
    }


    ll r = x0;
    inSquare = true;
    expAdd = 1;
    
    while (inSquare) {
        
        r += expAdd;
        if (r > N) {
            r -= expAdd;
            break;
        }

        inSquare = examine(r, y0);
        expAdd <<= 1;
    }

    if (inSquare) {
        inSquare = examine(N, y0);

        if (inSquare) {
            right = N;
        } else {
            right = binSearchBorderX(r, N, y0, false);
        }
    } else {
        expAdd >>= 1;
        right = binSearchBorderX(r-expAdd, r, y0, false);
    }



    ll M = right - left + 1;



    ll bottom = 1;

    ll b = y0;
    inSquare = true;
    expAdd = 1;

    while (inSquare) {
        b -= expAdd;
        if (b <= 0) {
            b += expAdd;
            break;
        }

        inSquare = examine(x0, b);
        expAdd <<= 1;
    }

    if (inSquare) {
        inSquare = examine(x0, 1);

        if (inSquare) {
            bottom = 1;
        } else {
            bottom = binSearchBorderY(1, b, x0);
        }
    } else {
        expAdd >>= 1;
        bottom = binSearchBorderY(b, b+expAdd, x0);
    }




    ll top = bottom + M - 1;

    ll currX = midpoint(left, right);
    ll currY = midpoint(bottom, top);


    while(currX - 2*M > 0 && examine(currX - 2*M, currY)) currX -= 2*M;
    while(currY - 2*M > 0 && examine(currX, currY - 2*M)) currY -= 2*M;

    while(currX - M > 0 && currY - M > 0 && examine(currX - M, currY - M)) {
        currX -= M;
        currY -= M;
    }


    ll midX = currX + 2*M;
    ll midY = currY + 2*M;

    printf("solution %lld %lld", midX, midY);
    fflush(stdout);

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'int main()':
aliens.cpp:58:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     ll N,x0, y0; scanf("%lld %lld %lld", &N, &x0,&y0);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...