Created
April 13, 2019 13:35
-
-
Save TimDumol/2ae2a7996c2fe08d495259f679989087 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <algorithm> | |
#include <bitset> | |
#include <cassert> | |
#include <cmath> | |
#include <complex> | |
#include <cstdio> | |
#include <cstdlib> | |
#include <cstring> | |
#include <functional> | |
#include <iostream> | |
#include <list> | |
#include <map> | |
#include <numeric> | |
#include <queue> | |
#include <set> | |
#include <string> | |
#include <utility> | |
#include <vector> | |
using namespace std; | |
using namespace __gnu_cxx; | |
typedef unsigned long long ullong; | |
typedef long long llong; | |
typedef list<int> EdgeList; | |
typedef vector<EdgeList> AdjList; | |
typedef pair<int, int> ii; | |
typedef vector<ii> vii; | |
#define FOR_EDGE(adj, v, it) \ | |
for (EdgeList::iterator it = adj[v].begin(); it != adj[v].end(); ++it) | |
#define FOR(v, it) for (auto it = v.begin(); it != v.end(); ++it) | |
int mat[32][32]; | |
int r, c; | |
int main() { | |
int n_cases; | |
cin >> n_cases; | |
for (int ctr = 0; ctr < n_cases; ++ctr) { | |
cin >> r >> c; | |
if (r == 2 && c <= 4 || r == 3 && c <= 3) { | |
printf("Case #%d: IMPOSSIBLE\n", ctr + 1); | |
continue; | |
} | |
memset(mat, 0, sizeof(mat)); | |
vector<int> rowv; | |
vector<int> colv; | |
for (int y = 0; y < r; ++y) { | |
rowv.push_back(y); | |
} | |
for (int x = 0; x < c; ++x) { | |
colv.push_back(x); | |
} | |
bool good = false; | |
const int steps = 1 << 10; | |
int lower = 1; | |
int px = c / 2; | |
int py = r / 2; | |
mat[py][px] = 1; | |
for (int step = 2; step < steps; ++step) { | |
random_shuffle(rowv.begin(), rowv.end()); | |
random_shuffle(colv.begin(), colv.end()); | |
for (; lower <= step; ++lower) { | |
bool found = false; | |
for (int y : rowv) { | |
if (y == py) { | |
continue; | |
} | |
for (int x : colv) { | |
if (x == px || x + y == px + py || x - y == px - py) continue; | |
if (mat[y][x] >= lower) continue; | |
mat[y][x] = step; | |
py = y; | |
px = x; | |
found = true; | |
break; | |
} | |
if (found) { | |
break; | |
} | |
} | |
if (found) break; | |
} | |
#ifdef DEBUG | |
printf("STEP %d\n", step); | |
for (int y = 0; y < r; ++y) { | |
for (int x = 0; x < c; ++x) { | |
printf("%4d ", mat[y][x]); | |
} | |
printf("\n"); | |
} | |
fflush(stdout); | |
cout.flush(); | |
#endif | |
if (mat[py][px] != step) break; | |
if (step - lower + 1 == r * c) { | |
good = true; | |
break; | |
} | |
} | |
#ifdef DEBUG | |
printf("finale\n"); | |
for (int y = 0; y < r; ++y) { | |
for (int x = 0; x < c; ++x) { | |
printf("%4d ", mat[y][x]); | |
} | |
printf("\n"); | |
} | |
#endif | |
if (good) { | |
printf("Case #%d: POSSIBLE\n", ctr + 1); | |
vector<tuple<int, int, int>> ans; | |
ans.reserve(r * c); | |
for (int y = 0; y < r; ++y) { | |
for (int x = 0; x < c; ++x) { | |
ans.emplace_back(mat[y][x], x, y); | |
} | |
} | |
sort(ans.begin(), ans.end()); | |
for (auto p : ans) { | |
int d, x, y; | |
tie(d, x, y) = p; | |
printf("%d %d\n", y + 1, x + 1); | |
} | |
} else { | |
printf("Case #%d: IMPOSSIBLE\n", ctr + 1); | |
} | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment