| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 148120 | WhipppedCream | Aliens (IOI07_aliens) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "alienslib.h"
#define ii pair<long long, long long>
#define X first
#define Y second
#define pb push_back
#define vi vector<long long>
#define vii vector< pair<long long, long long> >
typedef long long ll;
using namespace std;
char dump[100];
int n;
//long long __XC, __YC, __M;
/*bool works(long long X, long long Y)
{
long long x0 = __XC - __M - __M - __M/2;
long long y0 = __YC - __M - __M - __M/2;
long long dx = X - x0;
long long dy = Y - y0;
if (dx < 0 || dy < 0 || dx >= 5*__M || dy >= 5*__M)
return 0;
else
{
dx = dx / __M;
dy = dy / __M;
if ((dx+dy) % 2 == 0)
return 1;
else
return 0;
}
}*/
bool isFlat(int x, int y)
{
//return works(x, y);
if(x<= 0 || x> n || y<= 0 || y> n) return false;
return examine(x, y);
}
ii Right(long long x0, long long y0)
{
long long dx = 1;
long long white = 0;
long long last = x0;
while(1)
{
if(!isFlat(x0+dx, y0))
{
white = x0+dx;
break;
}
else
{
last = x0+dx;
dx *= 2;
}
}
long long left = last, right = white-1;
while(left< right)
{
long long mid = (left+right+1)/2;
if(isFlat(mid, y0)) left = mid;
else right = mid-1;
}
return ii(left, y0);
}
ii Left(long long x0, long long y0)
{
long long dx = 1;
long long white = 0;
long long last = x0;
while(1)
{
if(!isFlat(x0-dx, y0))
{
white = x0-dx;
break;
}
else
{
last = x0-dx;
dx = dx*2;
}
}
long long left = white+1, right = last;
while(left< right)
{
long long mid = (left+right)/2;
if(isFlat(mid, y0)) right = mid;
else left = mid+1;
}
return ii(left, y0);
}
ii Up(long long x0, long long y0)
{
long long dx = 1;
long long white = 0;
long long last = y0;
while(1)
{
if(!isFlat(x0, y0+dx))
{
white = y0+dx;
break;
}
else
{
last = y0+dx;
dx = dx*2;
}
}
long long lo = last, hi = white-1;
while(lo< hi)
{
long long mid = (lo+hi+1)/2;
if(isFlat(x0, mid)) lo = mid;
else hi = mid-1;
}
return ii(x0, lo);
}
int main()
{
int x0, y0;
//scanf("%lld %lld %lld %lld %lld %lld", &n, &__M, &x0, &y0, &__XC, &__YC);
get_size_and_start(n, x0, y0);
ii L = Left(x0, y0);
ii R = Right(x0, y0);
ii U = Up(x0, y0);
long long m = R.X-L.X+1;
ii D = ii(U.X, U.Y-m+1);
ii C = ii((L.X+R.X)/2, (U.Y+D.Y)/2);
long long below = 0;
for(long long i = 1; ; i++)
{
long long k = isFlat(C.X, C.Y-2*i*m);
if(k) below++;
else break;
}
long long leftside = 0;
for(long long i = 1; ; i++)
{
long long k = isFlat(C.X-2*i*m, C.Y);
if(k) leftside++;
else break;
}
long long rightside = 0;
for(long long i = 1; ; i++)
{
long long k = isFlat(C.X+2*i*m, C.Y);
if(k) rightside++;
else break;
}
long long above = 0;
for(long long i = 1; ; i++)
{
long long k = isFlat(C.X, C.Y+2*i*m);
if(k) above++;
else break;
}
long long hor = 1+leftside+rightside;
long long ver = 1+above+below;
long long p, q;
if(below == 2) p = 1;
else if(below == 1)
{
if(hor == 3) p = 3;
else p = 2;
}
else
{
if(hor == 3) p = 5;
else p = 4;
}
if(rightside == 2) q = 1;
else if(rightside == 1)
{
if(ver == 3) q = 3;
else q = 2;
}
else
{
if(ver == 3) q = 5;
else q = 4;
}
C = ii(C.X-(q-3)*m, C.Y-(3-p)*m);
solution(C.X, C.Y);
fflush(stdout);
return 0;
}