QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#53434#2615. Surround the CatMIT01#WA 10ms3732kbC++3.0kb2022-10-05 10:45:082022-10-05 10:45:11

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-05 10:45:11]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:3732kb
  • [2022-10-05 10:45:08]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define mod 998244353
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
#define ar2 array<int, 2>
using namespace std;
const int maxn = 4005;
const int S = 40;
map<ar2, int> dis;
int caldis(ar2 x) {
    int ans = 1e9;
    if (dis.count(x)) return dis[x];
    for (int j = -S; j <= S; j++) 
        chkmin(ans, abs(j) + abs(x[0] + j) + abs(x[1] + j));
    return dis[x] = ans;
}
map<ar2, int> cov;
set<ar2> bd;
int base = 10;
ar2 x[6] = {{9, 0}, {9, 9}, {0, 9}, {-9, 0}, {-9, -9}, {0, -9}};
ar2 dir[6] = {{1, 0}, {1, 1}, {0, 1}, {-1, 0}, {-1, -1}, {0, -1}};
ar2 add(ar2 a, ar2 b) {
    return {a[0] + b[0], a[1] + b[1]};
}
int main() {
    for (int i = 0; i < 6; i++) {
        ar2 u = x[i], v = x[(i + 1) % 6];
        int h[2];
        for (int j = 0; j < 2; j++)
            h[j] = (u[j] - v[j]) / 9;
        for (int k = 0; k < 9; k++) {
            ar2 p = {u[0] - k * h[0], u[1] - k * h[1]};
            bd.insert(p);
        }
    }
    while (1) {
        ar2 u;
        cin >> u[0] >> u[1];
        int mstr = 1e9;
        ar2 ed = {-1, -1};
        for (auto v : bd) {
            if (cov[v]) continue;
            int adj = 0;
            int dis = caldis({v[0] - u[0], v[1] - u[1]});
           // cout << v[0] << " " << v[1] << " " << dis << endl;
            for (int j = 0; j < 6; j++) {
                ar2 res = add(v, dir[j]);
                if (!bd.count(res)) continue;
                if (cov[res]) adj += 1;
            }
            int str = 0;
            if (dis == 1) str = 1;
            else if (adj == 2 && dis >= 3) str = 100;
            else {
                if (dis == 2) str = dis + adj;
                else str = adj * 2 + dis;
            }
            if (chkmin(mstr, str)) {
                ed = v;
               // cout << "!!! " << dis << ' ' << adj << endl;
                //cout << "!!!" << ' ' << ed[0] << ' ' << ed[1] << endl;
            }
        }
        if (mstr > 1e8) {
            for (int j = 0; j < 6; j++) {
                ar2 nx = add(u, dir[j]);
                if (cov[nx]) continue;
                mstr = 0;
                ed = nx;
                break;
            }
        }
        if (mstr > 1e7) break;
        cout << ed[0] << ' ' << ed[1] << endl;
        fflush(stdout);
        cov[ed] = 1;
        int end = 1;
        for (int j = 0; j < 6; j++) {
            ar2 nx = add(u, dir[j]);
            if (cov[nx])
                continue;
            end = 0;
        }
        if (end) break;
    }
    return 0;
}
/*
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

input:

0 0
1 0
2 1
3 1
4 1
5 1
6 2
7 2
7 3
7 2
7 1
7 0
7 1
7 2
7 1
7 0
7 1
7 2
7 1
7 0
6 -1
5 -2
4 -3
3 -4
4 -3
5 -2
6 -1
5 -2
4 -3
3 -4
2 -5
1 -6
0 -7
1 -6
0 -7
-1 -7
0 -7
1 -6
0 -7
1 -6
2 -5
1 -6
0 -7
-1 -7
0 -7
-1 -7
0 -7
1 -6
2 -5
3 -4
2 -5
3 -4
4 -3
5 -2
5 -3
4 -3
3 -4
3 -5
2 -6
1 -7
0 -8
0 -7
0 -6
-1...

output:

-9 -9
1 -8
9 1
9 3
9 5
5 -4
7 -2
9 2
9 4
9 7
8 -1
9 0
3 -6
7 9
9 9
-2 -9
5 9
-4 -9
-1 -9
-6 -9
6 -3
3 9
4 -5
-9 -7
-9 -5
-9 -3
-9 -1
-7 -9
1 9
-8 1
2 -7
-6 3
0 -9
-4 5
-2 7
-3 -9
-1 8
-9 -8
-9 -6
-9 -4
-9 -2
-9 0
-8 -9
-7 2
-5 -9
-5 4
-3 6
0 9
2 9
4 9
6 9
8 9
9 6
9 8
6 -2
5 -3
4 -4
3 -4
3 -5
2 -6
1 ...

result:

ok There is no valid neighbouring location.

Test #2:

score: 0
Accepted
time: 9ms
memory: 3704kb

input:

0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
1 7
0 7
1 7
0 7
1 7
0 7
1 7
2 7
1 7
2 7
1 7
2 7
1 7
2 7
3 7
2 7
1 7
2 7
1 7
2 7
1 7
2 7
1 7
2 7
1 7
2 7
1 7
2 7
1 7
2 7
1 7
2 7
1 7
0 7
-1 6
-2 5
-3 4
-4 3
-5 2
-6 1
-5 2
-6 1
-7 0
-7 -1
-7 -2
-7 -1
-6 0
-5 1
-5 2
-6 1
-7 0
-7 -1
-8 -2
-8 -1
-7 0
-8 0
-8 -1
-8 -2
-8 -...

output:

-9 -9
-8 1
-6 3
-4 5
-2 7
0 9
2 9
-1 8
3 9
1 9
5 9
7 9
9 7
-9 -2
9 9
4 9
9 5
-9 -4
-9 -1
9 3
-9 -6
9 1
3 -6
5 -4
1 -8
7 -2
-9 -7
-7 -9
-5 -9
-3 -9
-1 -9
8 -1
-9 -8
-9 -5
-9 -3
-9 0
-8 -9
-7 2
-6 -9
-5 4
-4 -9
-3 6
-2 -9
0 -9
2 -7
4 -5
6 -3
6 9
8 9
9 0
9 2
9 4
9 6
9 8
-5 0
-4 1
-4 2
-5 1
-6 0
-6 -1
-...

result:

ok There is no valid neighbouring location.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

0 0
-1 -1
-2 -2
-3 -3
-4 -4
-5 -5
-5 -6
-6 -7
-7 -7
-7 -6
-7 -5
-7 -6
-7 -7
-7 -6
-7 -7
-7 -6
-7 -5
-7 -4
-7 -5
-7 -4
-7 -5
-7 -6
-7 -5
-7 -6
-7 -5
-7 -4
-7 -5
-7 -6
-7 -5
-7 -4
-7 -5
-7 -6
-7 -5
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -5
-7 -6
-7 -7
-7 -6
-7...

output:

-9 -9
-9 -7
-9 -5
-9 -3
-7 -9
-5 -9
-3 -9
-8 -9
-9 -8
-9 -6
-9 -1
-8 1
-1 -9
-6 3
1 -8
3 -6
-4 5
-9 -4
-2 7
5 -4
0 9
7 -2
2 9
4 9
6 9
8 9
9 0
9 2
9 4
9 6
9 8
-9 -2
-9 0
-7 2
-6 -9
-5 4
-4 -9
-3 6
-2 -9
-1 8
0 -9
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-5 -1
-5 0
-6 0
-5 1
-4 2
-3 3
-...

result:

ok There is no valid neighbouring location.

Test #4:

score: 0
Accepted
time: 9ms
memory: 3500kb

input:

0 0
0 -1
0 -2
0 -3
0 -4
0 -5
0 -6
0 -7
-1 -7
0 -7
-1 -7
0 -7
1 -6
0 -7
-1 -7
0 -7
-1 -7
0 -7
1 -6
0 -7
-1 -7
0 -7
-1 -7
0 -7
-1 -7
0 -7
-1 -7
0 -7
-1 -7
0 -7
-1 -7
0 -7
-1 -7
0 -7
-1 -7
0 -7
1 -6
0 -7
-1 -7
0 -7
-1 -7
-2 -7
-3 -7
-4 -7
-5 -7
-6 -7
-7 -7
-7 -6
-7 -7
-7 -6
-7 -5
-7 -4
-7 -3
-7 -2
-6 -...

output:

-9 -9
-7 -9
-5 -9
-3 -9
-1 -9
1 -8
3 -6
-2 -9
5 -4
0 -9
-9 -7
2 -7
7 -2
9 0
-9 -5
9 2
9 4
-9 -3
9 6
-9 -1
-8 1
9 8
-6 3
-4 5
-2 7
0 9
2 9
4 9
6 9
8 9
-9 -8
-9 -6
-9 -4
-9 -2
-9 0
-8 -9
-7 2
-6 -9
-5 4
-4 -9
-3 6
-1 8
1 9
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-5 -1
-4 0
-5 0
-5 1
-5 2
-6 2
-...

result:

ok There is no valid neighbouring location.

Test #5:

score: 0
Accepted
time: 8ms
memory: 3708kb

input:

0 0
-1 0
-2 -1
-3 -1
-4 -1
-5 -2
-6 -3
-7 -3
-7 -4
-7 -5
-7 -6
-7 -7
-6 -7
-5 -7
-6 -7
-7 -7
-7 -6
-7 -7
-7 -6
-7 -5
-7 -6
-7 -5
-7 -6
-7 -7
-6 -7
-7 -7
-7 -6
-7 -7
-7 -6
-7 -5
-7 -6
-7 -7
-6 -7
-5 -7
-4 -7
-5 -7
-6 -7
-7 -7
-6 -7
-5 -7
-4 -7
-5 -7
-4 -7
-5 -7
-6 -7
-5 -7
-6 -7
-7 -7
-6 -7
-5 -7
-4 ...

output:

-9 -9
-9 -7
-9 -5
-9 -3
-9 -1
-8 1
-7 -9
-9 -4
-9 -6
-5 -9
-9 -8
-8 -9
-6 -9
-3 -9
-1 -9
1 -8
-6 3
3 -6
-4 5
-2 7
5 -4
0 9
7 -2
2 9
9 0
4 9
6 9
8 9
9 2
9 4
9 6
9 8
-9 -2
-9 0
-4 -9
-7 2
-5 4
-3 6
-2 -9
-1 8
0 -9
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-4 -8
-3 -7
-4 -7
-5 -8
-4 -6
-4...

result:

ok There is no valid neighbouring location.

Test #6:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

0 0
0 1
0 2
0 3
0 4
0 5
0 6
-1 6
0 7
-1 6
0 7
-1 6
-2 5
-1 6
0 7
-1 6
0 7
-1 6
-2 5
-1 6
0 7
-1 6
-2 5
-1 6
-2 5
-1 6
0 7
-1 6
-2 5
-1 6
0 7
-1 6
0 7
-1 6
0 7
-1 6
-2 5
-1 6
-2 5
-1 6
-2 5
-3 4
-4 3
-5 2
-6 1
-7 0
-6 1
-7 0
-6 1
-7 0
-7 -1
-7 -2
-7 -1
-7 0
-6 0
-6 1
-6 0
-6 -1
-7 -1
-8 -2
-8 -1
-8 0...

output:

-9 -9
-8 1
-6 3
-4 5
-2 7
0 9
2 9
-3 6
-1 8
4 9
1 9
6 9
-9 -2
8 9
9 7
-9 -4
-9 -1
9 5
-9 -6
9 8
9 3
-9 -7
-7 -9
-5 -9
-3 -9
-1 -9
9 1
1 -8
3 -6
5 -4
7 -2
8 -1
-9 -8
-9 -5
-9 -3
-9 0
-8 -9
-7 2
-6 -9
-5 4
-4 -9
-2 -9
0 -9
2 -7
3 9
4 -5
5 9
6 -3
7 9
9 0
9 2
9 4
9 6
9 9
-5 0
-5 1
-6 1
-5 -1
-6 -1
-7 -2...

result:

ok There is no valid neighbouring location.

Test #7:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

0 0
0 1
-1 1
-2 1
-2 2
-2 3
-3 3
-3 4
-4 3
-3 4
-2 5
-1 6
0 7
-1 6
-2 5
-3 4
-2 5
-1 6
-2 5
-3 4
-4 3
-3 4
-4 3
-5 2
-4 3
-3 4
-4 3
-5 2
-4 3
-3 4
-4 3
-3 4
-2 5
-1 6
0 7
1 7
0 7
1 7
0 7
1 7
0 7
-1 6
-2 5
-1 6
0 7
-1 6
-2 5
-3 4
-2 5
-1 6
-2 5
-1 6
0 7
-1 6
-1 5
0 6
-1 5
-1 6
-1 5
-1 4
-2 4
-3 3
-3 ...

output:

-9 -9
-8 1
-6 3
-4 5
-2 7
0 9
-9 -3
-5 4
-9 -1
-3 6
2 9
-1 8
1 9
4 9
6 9
-9 -5
8 9
9 6
9 8
-9 -7
-7 -9
9 4
-5 -9
-7 2
-3 -9
9 2
-1 -9
1 -8
3 -6
5 -4
7 -2
9 0
-9 -8
-9 -6
-9 -4
3 9
-9 -2
-9 0
-8 -9
-6 -9
-4 -9
-2 -9
0 -9
2 -7
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
0 5
1 6
0 6
0 7
-1 6
0 4
-1 4
-2...

result:

ok There is no valid neighbouring location.

Test #8:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

0 0
-1 -1
-1 -2
-1 -3
-2 -4
-2 -5
-2 -6
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-1 -7
-2 -7
-3 -7
-2 -7
-3 -7
-4 -7
-3 -7
-4 -7
-5 -7
-6 -7
-7 -7
-6 -7
-7 -7
-6 -7
-5 -7
-4 -7
-5 -7
-6 -7
-7 -7
-6 -7
-7 -7
-7 -6
-7 -5
-7 -6
-7 -7
-6 -7
-7 -7
-6 -7
-7 -7
-6 -7
-7 -7
-6 -7
-7 -7
-7 -6
-7 -5
-7 -6
-7 -5
-7...

output:

-9 -9
-9 -7
-7 -9
-5 -9
-3 -9
-1 -9
1 -8
-4 -9
-2 -9
3 -6
5 -4
-9 -5
7 -2
9 0
-9 -3
-9 -1
9 2
9 4
-6 -9
-8 1
-6 3
-4 5
-8 -9
-9 -8
-2 7
0 9
9 6
9 8
2 9
4 9
6 9
8 9
-9 -6
-9 -4
-9 -2
-9 0
-7 2
-5 4
-3 6
-1 8
0 -9
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-7 -5
-7 -4
-8 -4
-7 -6
-8 -6

result:

ok There is no valid neighbouring location.

Test #9:

score: 0
Accepted
time: 9ms
memory: 3476kb

input:

0 0
-1 0
-2 0
-3 0
-4 0
-5 0
-6 0
-7 0
-7 -1
-7 0
-7 -1
-7 0
-6 1
-5 2
-6 1
-5 2
-6 1
-5 2
-6 1
-5 2
-6 1
-7 0
-6 1
-5 2
-6 1
-5 2
-6 1
-7 0
-6 1
-7 0
-6 1
-7 0
-6 1
-5 2
-6 1
-7 0
-7 -1
-7 -2
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -5
-7 -6
-7 -7
-7 -6
-7 -5
-7 -4
-7 -3
-7 -2
-8 -3
-7 -2...

output:

-9 -9
-9 -7
-9 -5
-9 -3
-9 -1
-8 1
-6 3
-9 -2
-4 5
-9 0
-7 -9
-7 2
-2 7
-5 4
0 9
2 9
4 9
-5 -9
6 9
-3 -9
8 9
-1 -9
9 1
9 3
9 5
9 7
1 -8
3 -6
5 -4
7 -2
9 8
8 -1
-9 -8
-9 -6
-9 -4
-8 -9
-6 -9
-4 -9
-3 6
-2 -9
-1 8
0 -9
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
9 0
9 2
9 4
9 6
9 9
-7 -3
-6 -2
-6 -1
-7 -1
-7 -2
-7...

result:

ok There is no valid neighbouring location.

Test #10:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

0 0
-1 -1
-1 -2
-1 -3
-1 -4
-2 -5
-3 -6
-4 -7
-5 -7
-6 -7
-7 -7
-7 -6
-7 -7
-7 -6
-7 -7
-7 -6
-7 -7
-6 -7
-5 -7
-4 -7
-5 -7
-4 -7
-3 -7
-2 -7
-1 -7
0 -7
1 -6
2 -5
1 -6
0 -7
-1 -7
-2 -7
-1 -7
-2 -7
-1 -7
0 -7
1 -6
0 -7
1 -6
0 -7
1 -6
2 -5
1 -6
2 -5
1 -6
0 -7
1 -6
0 -7
-1 -7
-2 -7
-1 -7
-2 -7
-1 -7
0 ...

output:

-9 -9
-9 -7
-7 -9
-5 -9
-3 -9
-1 -9
1 -8
-6 -9
-9 -5
-8 -9
-9 -8
-9 -6
-9 -3
-9 -1
-8 1
-6 3
3 -6
5 -4
-4 5
-4 -9
7 -2
9 0
9 2
-2 -9
9 4
0 -9
2 -7
4 -5
9 6
9 8
-2 7
0 9
2 9
4 9
6 9
8 9
-9 -4
-9 -2
-9 0
-7 2
-5 4
-3 6
-1 8
1 9
3 9
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
1 -6
1 -5
0 -5
0 -6
-1 -6
-2 -7
...

result:

ok There is no valid neighbouring location.

Test #11:

score: 0
Accepted
time: 7ms
memory: 3732kb

input:

0 0
0 -1
-1 -2
-1 -3
-1 -4
-1 -5
-1 -6
-1 -7
0 -7
-1 -7
-2 -7
-1 -7
0 -7
1 -6
0 -7
1 -6
2 -5
1 -6
0 -7
1 -6
0 -7
-1 -7
0 -7
-1 -7
-2 -7
-1 -7
-2 -7
-3 -7
-2 -7
-3 -7
-4 -7
-3 -7
-4 -7
-5 -7
-4 -7
-5 -7
-4 -7
-5 -7
-6 -7
-7 -7
-7 -6
-7 -7
-6 -7
-5 -7
-6 -7
-5 -7
-4 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-4...

output:

-9 -9
-7 -9
-5 -9
-3 -9
-1 -9
1 -8
3 -6
-2 -9
0 -9
5 -4
-4 -9
-9 -7
2 -7
7 -2
9 0
9 2
4 -5
9 4
-9 -5
9 6
-9 -3
-9 -1
9 8
-8 1
-6 3
-4 5
-2 7
0 9
2 9
4 9
-6 -9
6 9
8 9
-9 -8
-9 -6
-9 -4
-9 -2
-9 0
-8 -9
-7 2
-5 4
-3 6
-1 8
1 9
3 9
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-1 -6
-2 -6
-1 -5
-1 -4
-2 -4
-2...

result:

ok There is no valid neighbouring location.

Test #12:

score: 0
Accepted
time: 6ms
memory: 3616kb

input:

0 0
-1 -1
-1 -2
-2 -3
-3 -4
-3 -5
-3 -6
-4 -7
-3 -7
-4 -7
-5 -7
-4 -7
-3 -7
-4 -7
-5 -7
-6 -7
-5 -7
-4 -7
-5 -7
-4 -7
-5 -7
-4 -7
-5 -7
-4 -7
-3 -7
-2 -7
-3 -7
-4 -7
-3 -7
-4 -7
-5 -7
-6 -7
-7 -7
-7 -6
-7 -7
-6 -7
-7 -7
-6 -7
-7 -7
-7 -6
-7 -5
-7 -4
-7 -5
-7 -6
-7 -7
-7 -6
-7 -5
-7 -4
-7 -3
-7 -4
-7...

output:

-9 -9
-9 -7
-7 -9
-5 -9
-3 -9
-9 -5
-1 -9
-6 -9
-4 -9
1 -8
-9 -3
3 -6
5 -4
-9 -1
-8 1
-8 -9
-6 3
7 -2
-4 5
9 0
-2 7
9 2
9 4
9 6
9 8
-2 -9
0 9
2 9
4 9
6 9
8 9
-9 -8
-9 -6
-9 -4
-9 -2
-9 0
-7 2
-5 4
-3 6
-1 8
0 -9
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-6 -8
-6 -7
-7 -8
-6 -6
-7 -7
-7...

result:

ok There is no valid neighbouring location.

Test #13:

score: 0
Accepted
time: 8ms
memory: 3652kb

input:

0 0
-1 0
-2 -1
-3 -2
-4 -3
-5 -4
-6 -5
-7 -6
-7 -7
-6 -7
-5 -7
-4 -7
-3 -7
-4 -7
-3 -7
-2 -7
-3 -7
-2 -7
-1 -7
0 -7
1 -6
2 -5
3 -4
4 -3
3 -4
4 -3
5 -2
4 -3
3 -4
4 -3
5 -2
6 -1
7 0
7 1
7 0
7 1
7 0
6 -1
7 0
6 -1
7 0
6 -1
7 0
6 -1
7 0
7 1
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 7
8 8
7 7
7 6
6 6
6 7
5 7
5 8
4 8
...

output:

-9 -9
-9 -7
-9 -5
-9 -3
-7 -9
-5 -9
-9 -1
-9 -8
-8 -9
-6 -9
-3 -9
-4 -9
-1 -9
1 -8
3 -6
-2 -9
5 -4
7 -2
9 0
0 -9
2 -7
4 -5
9 2
6 -3
9 4
9 6
9 8
4 9
6 9
8 9
2 9
8 -1
9 1
9 3
-8 1
-6 3
-4 5
-2 7
0 9
-9 -6
-9 -4
-9 -2
-9 0
-7 2
-5 4
-3 6
-1 8
1 9
3 9
9 5
5 9
9 7
7 9
9 9
7 8
8 7
8 6
7 6
7 7
6 7
6 8
5 8
...

result:

ok There is no valid neighbouring location.

Test #14:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

0 0
0 -1
0 -2
0 -3
0 -4
0 -5
0 -6
0 -7
-1 -7
0 -7
-1 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-1 -7
-2 -7
-3 -7
-4 -7
-5 -7
-6 -7
-7 -7
-7 -6
-7 -7
-7 -6
-7 -5
-7 -...

output:

-9 -9
-7 -9
-5 -9
-3 -9
-1 -9
1 -8
3 -6
-2 -9
5 -4
0 -9
-9 -7
-4 -9
-9 -5
7 -2
-9 -3
9 0
-9 -1
9 2
9 4
9 6
-8 1
-6 3
-4 5
-2 7
9 8
0 9
2 9
4 9
6 9
8 9
-9 -8
-9 -6
-9 -4
-9 -2
-9 0
-8 -9
-7 2
-6 -9
-5 4
-3 6
-1 8
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-6 -1
-5 0
-5 1
-6 1
-6 0
-6 2
-...

result:

ok There is no valid neighbouring location.

Test #15:

score: 0
Accepted
time: 8ms
memory: 3704kb

input:

0 0
0 -1
-1 -2
-1 -3
-1 -4
-2 -5
-3 -6
-3 -7
-4 -7
-3 -7
-4 -7
-3 -7
-4 -7
-5 -7
-4 -7
-5 -7
-4 -7
-5 -7
-4 -7
-3 -7
-4 -7
-5 -7
-4 -7
-5 -7
-4 -7
-3 -7
-4 -7
-3 -7
-2 -7
-1 -7
0 -7
1 -6
0 -7
-1 -7
-2 -7
-1 -7
-2 -7
-1 -7
0 -7
-1 -7
-2 -7
-1 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-1 -7
0 -7
1 -6
0 -7
-1 -...

output:

-9 -9
-7 -9
-5 -9
-3 -9
-1 -9
1 -8
-9 -7
-4 -9
-6 -9
3 -6
-9 -5
5 -4
-9 -3
-9 -1
7 -2
-8 1
-6 3
-4 5
9 0
9 2
9 4
-2 7
9 6
9 8
0 9
2 9
4 9
6 9
-2 -9
8 9
0 -9
2 -7
-9 -8
-9 -6
-9 -4
-9 -2
-9 0
-8 -9
-7 2
-5 4
-3 6
-1 8
1 9
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-1 -7
-2 -8
-1 -6
-2 -7
-1 -5
-1...

result:

ok There is no valid neighbouring location.

Test #16:

score: 0
Accepted
time: 5ms
memory: 3616kb

input:

0 0
0 -1
-1 -2
-1 -3
-2 -4
-2 -5
-3 -6
-4 -7
-5 -7
-4 -7
-5 -7
-4 -7
-3 -7
-2 -7
-3 -7
-4 -7
-3 -7
-4 -7
-5 -7
-6 -7
-5 -7
-6 -7
-7 -7
-6 -7
-5 -7
-4 -7
-3 -7
-4 -7
-5 -7
-6 -7
-5 -7
-6 -7
-5 -7
-4 -7
-5 -7
-4 -7
-5 -7
-4 -7
-5 -7
-4 -7
-3 -7
-4 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-1 -7
-2 -7
-3 ...

output:

-9 -9
-7 -9
-5 -9
-3 -9
-1 -9
1 -8
-9 -7
-6 -9
-9 -5
-4 -9
-9 -3
3 -6
5 -4
-2 -9
7 -2
-9 -1
9 0
-8 1
-6 3
-8 -9
-4 5
-2 7
-9 -8
9 2
9 4
9 6
9 8
0 9
2 9
4 9
6 9
8 9
-9 -6
-9 -4
-9 -2
-9 0
-7 2
-5 4
-3 6
-1 8
0 -9
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-2 -6
-3 -7
-3 -6
-4 -6
-4 -7
-5...

result:

ok There is no valid neighbouring location.

Test #17:

score: 0
Accepted
time: 4ms
memory: 3592kb

input:

0 0
-1 0
-2 0
-3 0
-4 0
-5 0
-6 0
-7 0
-7 -1
-7 -2
-7 -1
-7 -2
-7 -1
-7 -2
-7 -1
-7 -2
-7 -1
-7 -2
-7 -1
-7 -2
-7 -3
-7 -2
-7 -1
-7 -2
-7 -1
-7 -2
-7 -1
-7 -2
-7 -1
-7 -2
-7 -1
-7 -2
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -5
-7 -6
-7 -7
-7 -6
-7 -5
-7 ...

output:

-9 -9
-9 -7
-9 -5
-9 -3
-9 -1
-8 1
-6 3
-9 -2
-4 5
-9 -4
-7 -9
-5 -9
-2 7
-3 -9
0 9
2 9
4 9
-1 -9
6 9
1 -8
3 -6
5 -4
7 -2
8 9
9 0
9 2
9 4
9 6
9 8
-9 -8
-9 -6
-9 0
-8 -9
-7 2
-6 -9
-5 4
-4 -9
-3 6
-2 -9
-1 8
0 -9
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-6 -5
-5 -4
-4 -3
-5 -3
-6 -4
-7...

result:

ok There is no valid neighbouring location.

Test #18:

score: 0
Accepted
time: 5ms
memory: 3696kb

input:

0 0
0 -1
0 -2
-1 -3
-2 -4
-3 -5
-4 -6
-5 -7
-6 -7
-5 -7
-4 -7
-3 -7
-2 -7
-3 -7
-2 -7
-1 -7
0 -7
1 -6
2 -5
3 -4
2 -5
3 -4
4 -3
5 -2
6 -1
5 -2
4 -3
5 -2
6 -1
5 -2
6 -1
5 -2
4 -3
3 -4
2 -5
3 -4
2 -5
3 -4
4 -3
5 -2
4 -3
5 -2
6 -1
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 6
7 7
7 6
6 5
7 6
8 7
7 6
7 7
6 6
5 6
4...

output:

-9 -9
-7 -9
-5 -9
-3 -9
-1 -9
-9 -7
-9 -5
-6 -9
-8 -9
1 -8
-4 -9
3 -6
-2 -9
5 -4
7 -2
9 0
0 -9
2 -7
4 -5
9 2
9 4
9 6
6 -3
9 8
8 -1
5 9
7 9
3 9
8 9
-9 -3
-9 -1
1 9
-8 1
-6 3
-4 5
-2 7
-1 8
-9 -8
-9 -6
-9 -4
-9 -2
-9 0
-7 2
9 1
9 3
-5 4
9 5
-3 6
9 7
0 9
9 9
2 9
4 9
6 9
7 5
8 6
8 8
8 7
7 8
7 6
6 6
5 6
...

result:

ok There is no valid neighbouring location.

Test #19:

score: 0
Accepted
time: 9ms
memory: 3572kb

input:

0 0
1 1
1 2
2 3
3 4
3 5
3 6
3 7
2 7
3 7
4 7
5 7
6 7
7 7
7 6
7 7
6 7
5 7
4 7
5 7
4 7
3 7
4 7
3 7
2 7
1 7
0 7
1 7
2 7
3 7
4 7
5 7
4 7
5 7
4 7
5 7
4 7
3 7
2 7
1 7
2 7
1 7
2 7
3 7
2 7
3 7
2 7
1 7
0 7
1 7
2 7
3 7
2 7
3 7
3 8
3 7
2 6
1 5
1 6
0 5
0 6
-1 5
-1 4
-2 3
-1 4
-2 3
-2 4
-3 3
-3 2
-3 3
-3 2
-4 1
-...

output:

-9 -9
1 9
3 9
5 9
7 9
9 5
-3 6
4 9
-1 8
9 7
6 9
9 9
8 9
9 8
9 6
9 3
9 1
-5 4
-7 2
5 -4
7 -2
-9 -5
-9 -3
-9 -1
2 9
-8 1
-2 7
-9 -7
2 -7
3 -6
8 -1
-7 -9
-5 -9
-3 -9
-1 -9
1 -8
-9 -8
-9 -6
-9 -4
-9 -2
-9 0
-8 -9
-6 -9
-6 3
-4 -9
-4 5
-2 -9
0 -9
0 9
4 -5
6 -3
9 0
9 2
9 4
4 8
4 7
3 6
2 5
2 6
1 5
1 6
0 5
...

result:

ok There is no valid neighbouring location.

Test #20:

score: 0
Accepted
time: 9ms
memory: 3692kb

input:

0 0
1 0
2 0
3 0
4 0
4 -1
4 -2
5 -2
4 -3
5 -2
4 -3
5 -2
4 -3
3 -4
2 -5
3 -4
2 -5
1 -6
2 -5
1 -6
2 -5
3 -4
4 -3
3 -4
4 -3
5 -2
6 -1
5 -2
4 -3
3 -4
4 -3
5 -2
4 -3
5 -2
6 -1
5 -2
4 -3
5 -2
6 -1
5 -2
6 -1
5 -2
6 -1
7 0
7 1
7 2
7 1
7 2
7 1
7 0
6 -1
5 -2
4 -3
3 -4
4 -3
4 -4
3 -4
2 -5
2 -4
3 -3
2 -4
2 -5
2 ...

output:

-9 -9
1 -8
3 -6
5 -4
7 -2
9 0
9 2
6 -3
4 -5
9 4
-2 -9
9 6
-4 -9
-1 -9
2 -7
-6 -9
-9 -7
-7 -9
-9 -5
-9 -3
9 8
3 9
5 9
7 9
8 9
-9 -1
8 -1
1 9
-8 1
-6 3
-4 5
-2 7
-1 8
-9 -8
-9 -6
-9 -4
-9 -2
-9 0
-8 -9
-7 2
-5 -9
-5 4
-3 -9
9 1
9 3
-3 6
0 -9
0 9
2 9
4 9
6 9
9 5
9 7
9 9
5 -3
4 -3
4 -4
3 -5
3 -4
4 -2
3 ...

result:

ok There is no valid neighbouring location.

Test #21:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

0 0
-1 0
-2 -1
-3 -1
-4 -1
-5 -2
-6 -2
-7 -2
-7 -3
-7 -2
-7 -1
-7 -2
-7 -3
-7 -4
-7 -5
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -5
-7 -6
-7 -5
-7 -6
-7 -7
-6 -7
-5 -7
-4 -7
-5 -7
-6 -7
-5 -7
-4 -7
-3 -7
-4 -7
-3 -7
-4 -7
-3 -7
-4 -7
-3 -7
-2 -7
-1 -7
0 -7
1 -6
2 -5
1 -6
2 -5
1 -6
0 -7
-1 -7
-2 -...

output:

-9 -9
-9 -7
-9 -5
-9 -3
-9 -1
-8 1
-6 3
-9 -4
-7 -9
-9 -2
-4 5
-5 -9
-3 -9
-9 -6
-1 -9
-2 7
0 9
1 -8
2 9
3 -6
4 9
5 -4
6 9
-9 -8
7 -2
8 9
-8 -9
-6 -9
9 0
-4 -9
9 2
9 4
9 6
9 8
-9 0
-7 2
-5 4
-3 6
-2 -9
-1 8
0 -9
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-4 -7
-5 -7
-5 -6
-4 -5
-4 -4
-5...

result:

ok There is no valid neighbouring location.

Test #22:

score: 0
Accepted
time: 10ms
memory: 3648kb

input:

0 0
1 1
2 2
3 3
4 3
5 3
6 3
7 4
7 3
7 4
7 3
7 4
7 3
7 2
7 1
7 2
7 3
7 4
7 5
7 6
7 7
6 7
7 7
6 7
5 7
6 7
5 7
4 7
5 7
4 7
3 7
4 7
5 7
6 7
5 7
6 7
7 7
7 6
7 7
7 6
7 5
7 6
7 7
6 7
7 7
7 6
7 5
7 6
7 7
7 6
7 7
7 6
7 7
7 6
7 7
6 6
7 7
6 6
5 6
5 7
6 8
5 8
4 8
4 7
4 6
3 5
2 4
2 3
1 2
0 2
-1 1
-1 2
-2 2
-2 3
...

output:

-9 -9
1 9
3 9
5 9
9 3
9 5
9 7
9 4
9 1
9 6
7 -2
7 9
9 9
9 2
5 -4
8 -1
3 -6
-5 4
-3 6
9 8
8 9
6 9
-1 8
-7 2
-9 -7
-9 -5
-9 -3
4 9
-9 -1
-8 1
1 -8
-7 -9
-5 -9
-3 -9
-1 -9
-9 -8
-9 -6
-9 -4
-9 -2
-9 0
-8 -9
-6 -9
-6 3
-4 -9
-4 5
-2 -9
-2 7
0 -9
0 9
2 -7
2 9
4 -5
6 -3
9 0
8 7
7 6
8 8
7 7
6 6
6 7
7 8
6 8
...

result:

ok There is no valid neighbouring location.

Test #23:

score: 0
Accepted
time: 8ms
memory: 3732kb

input:

0 0
0 -1
0 -2
0 -3
0 -4
0 -5
0 -6
0 -7
-1 -7
0 -7
-1 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-3 -7
-2 -7
-1 -7
0 -7
-1 -7
-2 -7
-3 -7
-4 -7
-5 -7
-6 -7
-7 -7
-7 -6
-7 -7
-7 -6
-7 -5
-7 -4...

output:

-9 -9
-7 -9
-5 -9
-3 -9
-1 -9
1 -8
3 -6
-2 -9
5 -4
0 -9
-9 -7
-4 -9
-9 -5
7 -2
-9 -3
9 0
-9 -1
9 2
9 4
9 6
-8 1
-6 3
-4 5
-2 7
9 8
0 9
2 9
4 9
6 9
8 9
-9 -8
-9 -6
-9 -4
-9 -2
-9 0
-8 -9
-7 2
-6 -9
-5 4
2 -7
-3 6
-1 8
1 9
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-6 -3
-7 -4
-7 -3
-8 -3
-7 -5
-8...

result:

ok There is no valid neighbouring location.

Test #24:

score: 0
Accepted
time: 5ms
memory: 3636kb

input:

0 0
-1 0
-2 0
-3 -1
-4 -2
-5 -2
-6 -3
-7 -3
-7 -4
-7 -5
-7 -4
-7 -5
-7 -6
-7 -7
-7 -6
-7 -5
-7 -4
-7 -5
-7 -6
-7 -5
-7 -4
-7 -5
-7 -6
-7 -7
-6 -7
-5 -7
-4 -7
-5 -7
-4 -7
-5 -7
-4 -7
-3 -7
-4 -7
-5 -7
-6 -7
-7 -7
-7 -6
-7 -5
-7 -4
-7 -5
-7 -6
-7 -7
-7 -6
-7 -5
-7 -4
-7 -3
-7 -2
-7 -3
-7 -4
-7 -3
-7 -...

output:

-9 -9
-9 -7
-9 -5
-9 -3
-9 -1
-8 1
-7 -9
-9 -4
-9 -6
-5 -9
-6 3
-3 -9
-9 -8
-8 -9
-1 -9
-4 5
-2 7
1 -8
3 -6
5 -4
0 9
2 9
7 -2
4 9
-6 -9
9 0
-4 -9
9 2
9 4
9 6
9 8
6 9
8 9
-9 -2
-9 0
-7 2
-5 4
-3 6
-2 -9
-1 8
0 -9
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-7 -2
-7 -1
-7 0
-6 1
-7 1
-8 0
...

result:

ok There is no valid neighbouring location.

Test #25:

score: 0
Accepted
time: 7ms
memory: 3640kb

input:

0 0
-1 0
-2 0
-3 -1
-4 -1
-5 -2
-6 -3
-7 -3
-7 -4
-7 -3
-7 -2
-7 -1
-7 -2
-7 -3
-7 -4
-7 -5
-7 -4
-7 -5
-7 -6
-7 -5
-7 -4
-7 -3
-7 -4
-7 -5
-7 -6
-7 -5
-7 -6
-7 -7
-7 -6
-7 -7
-6 -7
-5 -7
-6 -7
-5 -7
-6 -7
-5 -7
-4 -7
-3 -7
-4 -7
-3 -7
-2 -7
-3 -7
-4 -7
-3 -7
-2 -7
-1 -7
-2 -7
-1 -7
-2 -7
-3 -7
-4 -...

output:

-9 -9
-9 -7
-9 -5
-9 -3
-9 -1
-8 1
-7 -9
-9 -4
-9 -6
-6 3
-9 -2
-4 5
-5 -9
-3 -9
-2 7
-1 -9
1 -8
3 -6
-9 -8
5 -4
0 9
2 9
4 9
6 9
7 -2
8 9
9 0
-8 -9
9 2
9 4
-6 -9
9 6
9 8
-9 0
-7 2
-5 4
-4 -9
-3 6
-2 -9
-1 8
0 -9
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-1 -7
-2 -7
-3 -8
-4 -8
-4 -7
-4...

result:

ok There is no valid neighbouring location.

Test #26:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

0 0
-1 0
-2 -1
-3 -1
-4 -2
-5 -2
-6 -2
-7 -3
-7 -4
-7 -5
-7 -4
-7 -5
-7 -4
-7 -5
-7 -4
-7 -5
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -5
-7 -4
-7 -3
-7 -2
-7 -1
-7 -2
-7 -1
-7 -2
-7 -1
-7 -2
-7 -3
-7 -2
-7 -1
-7 0
-6 1
-7 0
-6 1
-7 0
-6 1
-7 0
-7 -1
-7 -2
-7 -1
-7 -2
-7 -1
-7 0
-7 -1
-7 0
-7 -1
-7 -2
-7 -1
...

output:

-9 -9
-9 -7
-9 -5
-9 -3
-9 -1
-8 1
-6 3
-9 -4
-9 -6
-7 -9
-5 -9
-3 -9
-4 5
-1 -9
-2 7
1 -8
3 -6
0 9
5 -4
2 9
4 9
6 9
7 -2
8 9
-9 -2
9 0
9 2
9 4
9 6
9 8
-9 -8
-9 0
-8 -9
-7 2
-6 -9
-5 4
-4 -9
-3 6
-2 -9
-1 8
0 -9
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-5 0
-5 1
-6 0
-5 2
-6 1
-5 3
-6...

result:

ok There is no valid neighbouring location.

Test #27:

score: 0
Accepted
time: 4ms
memory: 3640kb

input:

0 0
0 -1
0 -2
-1 -3
-1 -4
-1 -5
-2 -6
-2 -7
-3 -7
-4 -7
-3 -7
-2 -7
-3 -7
-4 -7
-5 -7
-4 -7
-5 -7
-4 -7
-3 -7
-4 -7
-3 -7
-4 -7
-5 -7
-4 -7
-3 -7
-2 -7
-3 -7
-4 -7
-3 -7
-4 -7
-5 -7
-6 -7
-5 -7
-6 -7
-5 -7
-6 -7
-7 -7
-7 -6
-7 -5
-7 -4
-7 -3
-7 -4
-7 -5
-7 -6
-7 -5
-7 -6
-7 -7
-6 -7
-5 -7
-6 -7
-7 -...

output:

-9 -9
-7 -9
-5 -9
-3 -9
-1 -9
1 -8
3 -6
-4 -9
-9 -7
-6 -9
-9 -5
-2 -9
5 -4
-9 -3
-9 -1
7 -2
-8 1
-6 3
9 0
-4 5
9 2
9 4
-2 7
9 6
9 8
0 9
2 9
4 9
6 9
8 9
-9 -8
-8 -9
-9 -6
-9 -4
-9 -2
-9 0
-7 2
-5 4
-3 6
-1 8
0 -9
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-5 -5
-5 -6
-5 -4
-6 -6
-6 -7
-6...

result:

ok There is no valid neighbouring location.

Test #28:

score: 0
Accepted
time: 7ms
memory: 3692kb

input:

0 0
-1 0
-2 0
-3 -1
-4 -2
-5 -2
-6 -2
-7 -2
-7 -3
-7 -2
-7 -1
-7 -2
-7 -1
-7 -2
-7 -1
-7 -2
-7 -3
-7 -2
-7 -3
-7 -2
-7 -1
-7 0
-7 -1
-7 0
-7 -1
-7 -2
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -4
-7 -3
-7 -2
-7 -1
-7 0
-7 -1
-7 0
-6 1
-5 2
-4 3
-3 4
-2 5
-3 4
-2 5
-1 6
-2 5
-3 4
-4 3
-3 4
-4 3
-5 ...

output:

-9 -9
-9 -7
-9 -5
-9 -3
-9 -1
-8 1
-6 3
-9 -4
-7 -9
-9 -2
-4 5
-5 -9
-2 7
-3 -9
0 9
2 9
-1 -9
4 9
1 -8
6 9
3 -6
-9 0
5 -4
-7 2
7 -2
8 9
9 0
-9 -6
9 2
9 4
9 6
9 8
-9 -8
-8 -9
-6 -9
-5 4
-4 -9
-3 6
-2 -9
-1 8
0 -9
1 9
2 -7
3 9
4 -5
5 9
6 -3
7 9
8 -1
9 1
9 3
9 5
9 7
9 9
-5 2
-5 1
-6 1
-5 3
-6 2
-7 0
-7...

result:

ok There is no valid neighbouring location.

Test #29:

score: -100
Wrong Answer
time: 0ms
memory: 3560kb

input:

0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 8

output:

-9 -9
1 9
3 9
5 9
7 9
9 5
9 7
9 9
8 9
9 6

result:

wrong answer Cat reaches the boundary 9 8