Submission #1016937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016937		daffuwu	Aliens (IOI07_aliens)	C++14	100 / 100	1 ms	344 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

long long n, m, x0, y00, dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}, a1=3e9, b1=3e9, a2, b2, d, cx, cy;

bool ask(long long x, long long y)
{
    string res;
    printf("examine %lld %lld\n", x, y);
    fflush(stdout);
    cin >> res;
    return res == "true";
}

bool aman(long long x, long long y)
{
    return x>=1 && x<=n && y>=1 && y<=n;
}

long long determineBoundary(long long x, long long y, long long dir)
{
    long long i, cx, cy, msb=-1, res=0;
    for (i=0; i<=31; i++)
    {
        cx = x+dx[dir]*(1<<i);
        cy = y+dy[dir]*(1<<i);
        if (!aman(cx, cy) || !ask(cx, cy)) break;
        msb = i;
    }
    for (i=msb; i>=0; i--)
    {
        cx = x+dx[dir]*(1<<i);
        cy = y+dy[dir]*(1<<i);
        if (aman(cx, cy) && ask(cx, cy))
        {
            res += 1<<i;
            x = cx;
            y = cy;
        }
    }
    return res;
}

int main() 
{
    long long i;
    scanf("%lld%lld%lld", &n, &x0, &y00);
    for (i=0; i<=3; i++)
    {
        d = determineBoundary(x0, y00, i);
        cx = x0+dx[i]*d;
        cy = y00+dy[i]*d;
        a1 = min(a1, cx);
        b1 = min(b1, cy);
        a2 = max(a2, cx);
        b2 = max(b2, cy);
    }
    m = a2-a1+1;
    cx = a1;
    cy = b1;
    for(; aman(cx, cy-2*m) && ask(cx, cy-2*m); cy-=2*m);
    for (; aman(cx-2*m, cy) && ask(cx-2*m, cy); cx-=2*m);
    if (aman(cx-m, cy-m) && ask(cx-m, cy-m))
    {
        cx -= m;
        cy -= m;
    }
    cx += 2*m+m/2;
    cy += 2*m+m/2;
    printf("solution %lld %lld\n", cx, cy);
    fflush(stdout);
}

Compilation message (stderr)

aliens.cpp: In function 'int main()':
aliens.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%lld%lld%lld", &n, &x0, &y00);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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