#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include "coprobber.h"
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ii = pair<ll, ll>;
using ull = unsigned long long;
using vl = vector<long long>;
#define mp make_pair
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin() , (x).end()
#define vi vector<int>
const int N = 2*100005;
const long long MOD = 1000000007;
const long double EPS = 0.000000001;
const double PI = 3.14159265358979323846;
const long long INF = 10000000000000000;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0};
int dist(int x, int y, int a, int b) { return abs(x-a)+abs(y-b); }
long long gcd(int a, int b) { return (b==0?a:gcd(b, a%b)); }
long long lcm(int a, int b) { return a*(b/gcd(a, b)); }
long long fact(int a) { return (a==1?1:a*fact(a-1)); }
template<class T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#define MAX_N 500
vector<int>adj[MAX_N];
int police = 0;
int r, c; bool grid = 0;
bool check(int n) {
bool ok = true; int curr = 0; int l;
for(l = 0; l < n && curr < 2; l++) {
curr += ((int)adj[l].size() == 2);
ok &= ((int)adj[0].size() == 2);
if(l&&curr<2) ok &= ((int)adj[l].size() == 3);
}
ok &= (curr == 2);
return ok;
}
int start(int N, bool A[MAX_N][MAX_N])
{
for(int l = 0; l < N; l++) {
for(int i=0; i < N; i++) {
if(A[l][i]) adj[l].pb(i);
}
}
grid = check(N);
if(grid) c = adj[0][1], r = N/c;
return 0;
}
bool dfs(int v, int p, int dest) {
if(v == dest) return 1;
for(auto u:adj[v]) {
if(u == p) continue;
if(dfs(u, v, dest)) return 1;
}
return 0;
}
int nextMove(int R)
{
if(grid) {
int r1 = police / c, r2 = R / c;
int c1 = police % c, c2 = R % c;
int a = abs(r1 - r2), b = abs(c1 - c2);
if(a < b) {
int curr = 1e9, xx, yy;
for(int l = 0; l < 2; l++) {
int x = r1 + nx[l], y = c1 + ny[l];
int d = dist(x, y, r2, c1);
if(d < curr) xx = x, yy = y, curr = d;
}
return police = xx * c + yy;
}
else if(a > b) {
int curr = 1e9, xx, yy;
for(int l = 2; l < 4; l++) {
int x = r1 + nx[l], y = c1 + ny[l];
int d = dist(x, y, r2, c1);
if(d < curr) xx = x, yy = y, curr = d;
}
return police = xx * c + yy;
}
else if(a == b) return police;
}
for(auto u:adj[police]) {
if(u==R||dfs(u, police, R)) {
return police = u;
}
}
return -1;
}
Compilation message
coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:101:44: warning: 'yy' may be used uninitialized in this function [-Wmaybe-uninitialized]
101 | return police = xx * c + yy;
| ~~~~~~~^~~~
coprobber.cpp:101:40: warning: 'xx' may be used uninitialized in this function [-Wmaybe-uninitialized]
101 | return police = xx * c + yy;
| ~~~^~~
coprobber.cpp:92:44: warning: 'yy' may be used uninitialized in this function [-Wmaybe-uninitialized]
92 | return police = xx * c + yy;
| ~~~~~~~^~~~
coprobber.cpp:92:40: warning: 'xx' may be used uninitialized in this function [-Wmaybe-uninitialized]
92 | return police = xx * c + yy;
| ~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
200 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Correct |
0 ms |
328 KB |
Output is correct |
| 4 |
Correct |
52 ms |
1756 KB |
Output is correct |
| 5 |
Correct |
9 ms |
928 KB |
Output is correct |
| 6 |
Correct |
36 ms |
1520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
200 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Correct |
38 ms |
1536 KB |
Output is correct |
| 4 |
Correct |
37 ms |
1724 KB |
Output is correct |
| 5 |
Correct |
36 ms |
1568 KB |
Output is correct |
| 6 |
Correct |
48 ms |
1600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
200 KB |
Output is correct |
| 2 |
Correct |
0 ms |
200 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
0 ms |
200 KB |
Output is correct |
| 5 |
Correct |
0 ms |
328 KB |
Output is correct |
| 6 |
Correct |
0 ms |
200 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
200 KB |
Cop cannot catch the robber, but start() did not return -1 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
200 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Correct |
0 ms |
328 KB |
Output is correct |
| 4 |
Correct |
52 ms |
1756 KB |
Output is correct |
| 5 |
Correct |
9 ms |
928 KB |
Output is correct |
| 6 |
Correct |
36 ms |
1520 KB |
Output is correct |
| 7 |
Correct |
0 ms |
200 KB |
Output is correct |
| 8 |
Correct |
0 ms |
328 KB |
Output is correct |
| 9 |
Correct |
38 ms |
1536 KB |
Output is correct |
| 10 |
Correct |
37 ms |
1724 KB |
Output is correct |
| 11 |
Correct |
36 ms |
1568 KB |
Output is correct |
| 12 |
Correct |
48 ms |
1600 KB |
Output is correct |
| 13 |
Correct |
0 ms |
200 KB |
Output is correct |
| 14 |
Correct |
0 ms |
200 KB |
Output is correct |
| 15 |
Correct |
1 ms |
328 KB |
Output is correct |
| 16 |
Correct |
0 ms |
200 KB |
Output is correct |
| 17 |
Correct |
0 ms |
328 KB |
Output is correct |
| 18 |
Correct |
0 ms |
200 KB |
Output is correct |
| 19 |
Incorrect |
0 ms |
200 KB |
Cop cannot catch the robber, but start() did not return -1 |
| 20 |
Halted |
0 ms |
0 KB |
- |
