You are viewing a single comment's thread. Return to all comments →
C++14 Solution
#include <iostream> #include <vector> #include <queue> #include <tuple> #include <functional> #include <chrono> #include <cassert> #define repeat(i,n) for (int i = 0; (i) < int(n); ++(i)) #define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= int(m); --(i)) typedef long long ll; using namespace std; template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >; template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); } template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); } const int inf = 1e9+7; const int limit = 500; int goodness(vector<vector<int> > const & f) { int n = f.size(); int cnt = 0; repeat (y,n) repeat (xr,n) repeat (xl,xr) cnt += (f[y][xl] < f[y][xr]); repeat (x,n) repeat (yr,n) repeat (yl,yr) cnt += (f[yl][x] < f[yr][x]); return cnt; } vector<vector<int> > rotate(int y, int x, int k, vector<vector<int> > const & f) { vector<vector<int> > g = f; repeat (dy,k) repeat (dx,k) g[y+dx][x+k-dy-1] = f[y+dy][x+dx]; return g; } pair<int, int> find_cell(vector<vector<int> > const & f, int k) { int n = f.size(); repeat (y,n) repeat (x,n) if (f[y][x] == k) return { y, x }; assert (false); } bool is_next_fixed(int y, int x, vector<vector<bool> > const & fixed) { return (y == 0 or fixed[y-1][x]) and (x == 0 or fixed[y][x-1]); } void solve_fast(int n, vector<vector<int> > & f, vector<tuple<int, int, int> > & result) { vector<vector<bool> > fixed = vectors(n, n, bool()); vector<int> fixed_length(n); int next_fixed = 1; while (result.size() < limit*0.96 and next_fixed <= n*n) { int py, px; tie(py, px) = find_cell(f, next_fixed); if (is_next_fixed(py, px, fixed)) { fixed[py][px] = true; next_fixed += 1; } else { bool found = false; vector<vector<int> > dist = vectors(n, n, inf); vector<vector<tuple<int, int, int, int, int> > > path = vectors(n, n, tuple<int, int, int, int, int>()); reversed_priority_queue<tuple<int, int, int> > que; dist[py][px] = 0; que.emplace(0, py, px); auto commit = [&](int y, int x) { deque<tuple<int, int, int> > acc; while (y != py or x != px) { int ry, rx, rk; tie(y, x, ry, rx, rk) = path[y][x]; acc.emplace_front(ry, rx, rk); } if (result.size() + acc.size() > limit) return; for (auto it : acc) { int ry, rx, rk; tie(ry, rx, rk) = it; f = rotate(ry, rx, rk, f); result.push_back(it); } found = true; }; while (not que.empty()) { int z, y, x; tie(z, y, x) = que.top(); que.pop(); if (is_next_fixed(y, x, fixed)) { commit(y, x); break; } auto push = [&](int ny, int nx, int ry, int rx, int rk) { if (dist[ny][nx] != inf) return; dist[ny][nx] = z+1; path[ny][nx] = make_tuple(y, x, ry, rx, rk); que.emplace(z+1, ny, nx); }; for (int k = 2; y+k-1 < n and x+k-1 < n and not fixed[y ][x ]; ++ k) push(y, x+k-1, y, x, k); // right for (int k = 2; y+k-1 < n and x-k+1 >= 0 and not fixed[y ][x-k+1]; ++ k) push(y+k-1, x, y, x-k+1, k); // down for (int k = 2; y-k+1 >= 0 and x+k-1 < n and not fixed[y-k+1][x ]; ++ k) push(y-k+1, x, y-k+1, x, k); // up for (int k = 2; y-k+1 >= 0 and x-k+1 >= 0 and not fixed[y-k+1][x-k+1]; ++ k) push(y, x-k+1, y-k+1, x-k+1, k); // left } if (not found) break; } } } void solve_slow(int n, vector<vector<int> > & f, vector<tuple<int, int, int> > & result) { chrono::high_resolution_clock::time_point clock_begin = chrono::high_resolution_clock::now(); while (result.size() < limit) { chrono::high_resolution_clock::time_point clock_end = chrono::high_resolution_clock::now(); if (chrono::duration_cast<chrono::milliseconds>(clock_end - clock_begin).count() >= 1900) break; int best_y, best_x, best_k; int best = goodness(f); repeat (y,n) repeat (x,n) repeat_from_reverse (k,2,min(n-y,n-x)+1) { int z = goodness(rotate(y, x, k, f)); if (best < z) { best_y = y; best_x = x; best_k = k; best = z; } } if (best == goodness(f)) break; f = rotate(best_y, best_x, best_k, f); result.emplace_back(best_y, best_x, best_k); } } vector<tuple<int, int, int> > solve(int n, vector<vector<int> > f) { vector<tuple<int, int, int> > result; solve_fast(n, f, result); solve_slow(n, f, result); return result; } int main() { int n; cin >> n; vector<vector<int> > f = vectors(n, n, int()); repeat (y,n) repeat (x,n) cin >> f[y][x]; int gb = goodness(f); int gmax = n*n*(n-1); vector<tuple<int, int, int> > result = solve(n, f); cout << result.size() << endl; assert (result.size() <= 500); for (auto it : result) { int y, x, k; tie(y, x, k) = it; cout << y+1 << ' ' << x+1 << ' ' << k << endl; assert (0 <= y and y < n and 0 <= x and x < n and 1 <= k and max(y,x) + k <= n); f = rotate(y, x, k, f); } repeat (y,n) { repeat (x,n) cerr << (f[y][x] <= 9 ? " " : "") << f[y][x] << " "; cerr << endl; } cerr << "size: " << result.size() << endl; int ga = goodness(f); cerr << "points: " << ((ga - gb)/(double)(gmax - gb)) << endl; return 0; }
Sam's Puzzle (Approximate)
You are viewing a single comment's thread. Return to all comments →
C++14 Solution