Submission #1154657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154657		salmon	Aliens (IOI07_aliens)	C++20	100 / 100	1 ms	416 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
#define int long long

long long N;
long long X;
long long Y;
long long lX;
long long rX;
long long lY;
long long rY;
map<pair<int,int>,bool> mep;

bool inpoot(long long x, long long y){
    if(x < 1 || y < 1) return false;
    if(x > N || y > N) return false;
    if(mep.find({x,y}) != mep.end()) return mep[make_pair(x,y)];
    printf("examine %d %d\n",x,y);
    fflush(stdout);

    string s;

    cin >> s;

    return mep[{x,y}] = (s == "true");
}

int32_t main(){

    scanf(" %lld",&N);
    scanf(" %lld",&X);
    scanf(" %lld",&Y);

    int s = 1;

    bool can[2];

    can[0] = true;
    can[1] = true;

    while(true){
        if(can[0]){
            if(inpoot(s * 2 + X - 1,Y)) can[0] = true;
            else can[0] = false;
        }
        if(can[0]) s *= 2;
        else if(!inpoot(X - s + 1,Y)) break;
        else{
            if(can[1]){
                if(inpoot(X - s * 2 + 1,Y)) can[1] = true;
                else can[1] = false;
            }
            if(can[1]) s*= 2;
            else break;
        }
    }

    if(s != 1){
        lX = X;
        rX = X;

        while(inpoot(lX - s + 1,Y)) lX +=  - s + 1;
        while(inpoot(rX + s - 1,Y)) rX += s - 1;
    }
    else{
        lX = X;
        rX = X;
    }


//printf("%d %d\n",lX,rX);
    int ns = 0;
    int e = s - 1;

    while(ns != e){
        int m = (ns + e + 1)/2;

        if(inpoot(lX - m,Y)){
            ns = m;
        }
        else{
            e = m - 1;
        }
    }

    lX -= ns;

    ns = 0;
    e = s - 1;

    while(ns != e){
        int m = (ns + e + 1)/2;

        if(inpoot(rX + m,Y)){
            ns = m;
        }
        else{
            e = m - 1;
        }
    }

    rX += ns;

    int L = rX - lX + 1;
//printf("%d %d %d\n",lX,rX,L);
    lY = Y;
    rY = Y;

    ns = 0;
    e = L - 1;

    while(ns != e){
        int m = (ns + e + 1)/2;

        if(inpoot(X,lY - m)){
            ns = m;
        }
        else{
            e = m - 1;
        }
    }

    lY -= ns;
    rY = lY + L - 1;

    X = (rX + lX)/2;
    Y = (rY + lY)/2;

    int temp;

    int lcont = 0;
    int rcont = 0;

    while(inpoot(X - 2 * L * (1 + lcont), Y )) lcont++;
    while(inpoot(X + 2 * L * (1 + rcont), Y )) rcont++;

    rcont -= lcont;

    int x = X;

    X += rcont * L;

    lcont = 0;
    rcont = 0;

    while(inpoot(x,Y - 2 * L * (1 + lcont) )) lcont++;
    while(inpoot(x,Y + 2 * L * (1 + rcont) )) rcont++;

    rcont -= lcont;

    Y += rcont * L;

    printf("solution %lld %lld\n",X,Y);
}

Compilation message (stderr)

aliens.cpp: In function 'bool inpoot(long long int, long long int)':
aliens.cpp:18:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   18 |     printf("examine %d %d\n",x,y);
      |                     ~^       ~
      |                      |       |
      |                      int     long long int
      |                     %lld
aliens.cpp:18:25: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   18 |     printf("examine %d %d\n",x,y);
      |                        ~^      ~
      |                         |      |
      |                         int    long long int
      |                        %lld
aliens.cpp: In function 'int32_t main()':
aliens.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf(" %lld",&N);
      |     ~~~~~^~~~~~~~~~~~
aliens.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf(" %lld",&X);
      |     ~~~~~^~~~~~~~~~~~
aliens.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf(" %lld",&Y);
      |     ~~~~~^~~~~~~~~~~~

• 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