Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /****Author: Barish Namazov****/
- #include <bits/stdc++.h>
- using namespace std;
- /***TEMPLATE***/
- #define all(v) (v).begin(),(v).end()
- #define rall(v) (v).rbegin(),(v).rend()
- #define F first
- #define S second
- #define pb push_back
- #define endl '\n'
- const int max4 = 10004;
- const int maxx = 200005;
- const int max6 = 1000006;
- const int lg5 = 17;
- const int INF = 1000000007;
- const long long INFLL = 4LL * 1000000000 * 1000000000;
- /***************/
- int powmod (int a, int b, int mod) {
- int res = 1; a %= mod;
- for (; b; b >>= 1) {
- if (b & 1) {
- res = 1LL * res * a % mod;
- }
- a = 1LL * a * a % mod;
- }
- return res;
- }
- int gcd (int a, int b) {
- while (b > 0) {
- int t = a % b;
- a = b, b = t;
- }
- return a;
- }
- int lcm (int a, int b) {
- return (a / gcd (a, b)) * b;
- }
- int is_prime (int n) {
- if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
- return 0;
- for (int i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
- if (n % i == 0)
- return 0;
- return 1;
- }
- /******Don't forget to use long long when needed!!******/
- int n, m;
- vector <pair <int, int>> lol, emp;
- vector <vector <int>> loll;
- vector <pair <int, int>> go(int i, int j, int cnt, vector <pair <int, int>> v, vector <vector <int>> used) {
- v.pb({i, j});
- used[i][j] = 1;
- if (cnt == n * m) {
- return v;
- }
- vector <pair <int, pair <int, int>>> soxus;
- for (int ii = 1; ii <= n; ii++) {
- for (int jj = 1; jj <= m; jj++) {
- if (used[ii][jj] == 1 || i == ii || j == jj || i - j == ii - jj || i + j == ii + jj) continue;
- soxus.pb({abs(i - ii) + abs(j - jj), {ii, jj}});/*
- auto cur = go(ii, jj, cnt + 1, v, used);
- if (cur.size() > 0) {
- return cur;
- }*/
- }
- }
- if (soxus.size() > 0) {
- sort(all(soxus));
- auto x = soxus[0], y = soxus.back(); swap(x, y);
- auto cur1 = go(x.S.F, x.S.S, cnt + 1, v, used);
- if (cur1.size() > 0) return cur1;
- auto cur2 = go(y.S.F, y.S.S, cnt + 1, v, used);
- return cur2;
- }
- return emp;
- }
- int main() {
- //freopen("sleepy.in","r",stdin);
- //freopen("sleepy.out","w",stdout);
- ios_base :: sync_with_stdio(0);
- cin.tie(0), cout.tie(0);
- int T;
- cin >> T;
- for (int cs = 1; cs <= T; cs++) {
- cin >> n >> m;
- vector <pair <int, int>> res;
- loll = vector <vector <int>>(n + 1, vector <int>(m + 1));
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) {
- auto cur = go(i, j, 1, lol, loll);
- if (cur.size() > 0) {
- res = cur;
- break;
- }
- }
- if (res.size() > 0) break;
- }
- cout << "Case #" << cs << ": ";
- if (res.size() == 0) {
- cout << "IMPOSSIBLE" << endl;
- } else {
- cout << "POSSIBLE" << endl;
- for (auto x : res) {
- cout << x.F << " " << x.S << endl;
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement