#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifdef local
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define pary(a...) danb(#a, a)
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
int cnt = sizeof...(T);
((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
std::cerr << "\033[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L)
std::cerr << (f++ ? ", " : "") << *L;
std::cerr << " ]\033[0m\n";
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define pb emplace_back
#define get_pos(u,x) int(lower_bound(all(u),x)-begin(u))
using namespace std;
using ll = int_fast64_t;
using ld = long double;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
const int mod = 1000000007;
const int inf = 1e9;
const ll INF = 1e18;
const int maxn = 5025;
template <typename T> void sort_uni(T &v) { sort(all(v)), v.erase(unique(all(v)), v.end()); }
int calc(int R, int C, vector<pair<int,int>> pts) {
int N = pts.size();
auto solve = [&]() {
sort(all(pts));
vector<int> dx{0};
for (int i = 0; i < N; i++) {
for (int j = 0; j < i; j++) {
dx.emplace_back(pts[i].first - pts[j].first - 1);
}
dx.emplace_back(pts[i].first - 1);
dx.emplace_back(R - pts[i].first);
}
sort_uni(dx);
int mina = pts[0].first - 1;
int minb = R - pts[N-1].first;
int minsum = 0;
for (int i = 1; i < N; i++) minsum = max(minsum, pts[i].first - pts[i-1].first - 1);
int res = 2e9;
for (int a: dx) {
if (a < mina) continue;
for (int b: dx) {
if (b < minb) continue;
if (a + b < minsum) continue;
vector<pair<int,int>> evt;
for (auto [x, y]: pts) evt.emplace_back(x-a, y);
for (auto [x, y]: pts) evt.emplace_back(x+b+1, -y);
inplace_merge(evt.begin(), evt.begin() + N, evt.end());
multiset<int> posy;
multiset<int> diff;
auto add = [&](int val) {
auto it = posy.insert(val);
if (it != posy.begin() && next(it) != posy.end())
diff.erase(diff.find(*next(it) - *prev(it)));
if (it != posy.begin())
diff.insert(val - *prev(it));
if (next(it) != posy.end())
diff.insert(*next(it) - val);
};
auto remove = [&](int val) {
auto it = posy.find(val);
if (it != posy.begin())
diff.erase(diff.find(val - *prev(it)));
if (next(it) != posy.end())
diff.erase(diff.find(*next(it) - val));
if (it != posy.begin() && next(it) != posy.end())
diff.insert(*next(it) - *prev(it));
posy.erase(it);
};
int ans = 0, minc = 0, mind = 0;
for (int i = 0, j = 0; i < N*2; i = j) {
for (j = i; j < N*2; j++) {
if (evt[j].first != evt[i].first) break;
int y = evt[j].second;
if (y < 0) {
remove(-y);
} else {
add(y);
}
}
if (j == N*2) continue;
int l = evt[i].first;
int r = evt[j].first;
if (r <= 1 || l > R) continue;
assert (posy.size() > 0);
minc = max(minc, *posy.begin() - 1);
mind = max(mind, C - *prev(posy.end()));
if (diff.size())
ans = max(ans, *prev(diff.end()) - 1);
}
ans = max(ans, minc + mind);
// debug(a, b, ans);
// debug(minc, mind);
res = min(res, a + b + ans);
}
}
return res;
};
int res = solve();
for (auto &[x, y]: pts) swap(x, y);
return min(res, solve());
}
int naive(int R, int C, vector<pair<int,int>> pts) {
int grid = 0;
for (auto [x, y]: pts) grid |= 1<<((x-1) * C + (y-1));
unordered_map<int,int> dis;
const int U = (1 << (R*C)) - 1;
queue<int> q;
dis[grid] = 0;
q.push(grid);
int mask1 = 0, mask2 = 0;
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
if (j - 1 >= 0)
mask1 |= 1 << (i * C + j);
if (j + 1 < C)
mask2 |= 1 << (i * C + j);
}
while (!q.empty()) {
int cur = q.front(); q.pop();
if (int nxt = (cur | cur << C) & U; !dis.count(nxt))
dis[nxt] = dis[cur] + 1, q.push(nxt);
if (int nxt = (cur | cur >> C); !dis.count(nxt))
dis[nxt] = dis[cur] + 1, q.push(nxt);
if (int nxt = cur | ((cur & mask1) >> 1); !dis.count(nxt))
dis[nxt] = dis[cur] + 1, q.push(nxt);
if (int nxt = cur | ((cur & mask2) << 1); !dis.count(nxt))
dis[nxt] = dis[cur] + 1, q.push(nxt);
}
return dis[U];
}
void verify() {
int R, C;
cin >> R >> C;
for (int i = 1; i < (1<<(R*C)); i++) {
vector<pair<int,int>> pts;
for (int j = 0; j < R*C; j++) if (i >> j & 1) pts.emplace_back(j / C + 1, j % C + 1);
if (naive(R, C, pts) != calc(R, C, pts)) {
for (auto [x, y]: pts) cerr<<x<<','<<y<<'\n';
exit(3);
}
}
exit(0);
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
// verify();
int R, C, N;
cin >> R >> C >> N;
vector<pair<int,int>> pts(N);
for (auto &[x, y]: pts) cin >> x >> y;
cout << naive(R, C, pts) << '\n';
}
/*
4 4 2
1 2
2 1
*/
Compilation message
cultivation.cpp: In lambda function:
cultivation.cpp:63:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
63 | for (auto [x, y]: pts) evt.emplace_back(x-a, y);
| ^
cultivation.cpp:64:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
64 | for (auto [x, y]: pts) evt.emplace_back(x+b+1, -y);
| ^
cultivation.cpp: In function 'int calc(int, int, std::vector<std::pair<int, int> >)':
cultivation.cpp:119:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
119 | for (auto &[x, y]: pts) swap(x, y);
| ^
cultivation.cpp: In function 'int naive(int, int, std::vector<std::pair<int, int> >)':
cultivation.cpp:125:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
125 | for (auto [x, y]: pts) grid |= 1<<((x-1) * C + (y-1));
| ^
cultivation.cpp:141:13: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
141 | if (int nxt = (cur | cur << C) & U; !dis.count(nxt))
| ^~~
cultivation.cpp:144:13: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
144 | if (int nxt = (cur | cur >> C); !dis.count(nxt))
| ^~~
cultivation.cpp:147:13: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
147 | if (int nxt = cur | ((cur & mask1) >> 1); !dis.count(nxt))
| ^~~
cultivation.cpp:150:13: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
150 | if (int nxt = cur | ((cur & mask2) << 1); !dis.count(nxt))
| ^~~
cultivation.cpp: In function 'void verify()':
cultivation.cpp:162:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
162 | for (auto [x, y]: pts) cerr<<x<<','<<y<<'\n';
| ^
cultivation.cpp: In function 'int main()':
cultivation.cpp:175:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
175 | for (auto &[x, y]: pts) cin >> x >> y;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
