結果
問題 | No.2675 KUMA |
ユーザー |
![]() |
提出日時 | 2024-03-18 14:52:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,186 bytes |
コンパイル時間 | 5,338 ms |
コンパイル使用メモリ | 312,612 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-30 04:57:31 |
合計ジャッジ時間 | 8,735 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 45 WA * 2 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using mint = modint998244353; //多倍長整数// //#include <boost/multiprecision/cpp_int.hpp> //namespace mp = boost::multiprecision; //using bint = mp::cpp_int; const int INF = 2e9; const int MOD = 998244353; const long long LINF = 5e18; using ll = long long; using vi = vector<int>; using vl = vector<long long>; using vs = vector<string>; using vc = vector<char>; using vb = vector<bool>; using vvi = vector<vector<int>>; using vvvi = vector<vector<vector<int>>>; using vvvvi = vector<vector<vector<vector<int>>>>; using vvl = vector<vector<long long>>; using vvvl = vector<vector<vector<long long>>>; using vvvvl = vector<vector<vector<vector<long long>>>>; using vvc = vector<vector<char>>; using vvb = vector<vector<bool>>; using vvvb = vector<vector<vector<bool>>>; using vvvvb = vector<vector<vector<vector<bool>>>>; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define dump(x) cout << #x << " = " << (x) << endl; #define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl #define ALL(obj) (obj).begin(),(obj).end() int main(){ int n; cin >> n; vi x(n),y(n); rep(i,n) cin >> x[i] >> y[i]; vector<int> dp(1<<n,INF); int dx[8] = {2,2,1,-1,-2,-2,-1,1}; int dy[8] = {-1,1,2,2,1,-1,-2,-2}; dp[0] = 0; rep(i,1<<n){ rep(j,n){ if(i & (1<<j)) continue; rep(k,8){ bool ok = true; rep(l,n){ if(j == l) continue; if(i & (1<<l)) continue; if(x[j] + dx[k] == x[l] && y[j] + dy[k] == y[l]) ok = false; rep(m,8) if(x[j] + dx[k] + dx[m] == x[l] && y[j] + dy[k] + dy[m] == y[l]) ok = false; } if(ok){ dp[i | (1<<j)] = min(dp[i | (1<<j)],dp[i] + 1); break; } } } for(int j = 0;j < n - 1;j++){ if(i & (1<<j)) continue; for(int k = j + 1;k < n;k++){ if(i & (1<<k)) continue; if(x[j] == x[k] && y[j] + 2 == y[k]){ int nx = x[j] + 2,ny = y[j] + 1; bool ok = true; rep(l,n){ if(j == l) continue; if(k == l) continue; if(i & (1<<l)) continue; if(nx == x[l] && ny == y[l]) ok = false; rep(m,8) if(nx + dx[m] == x[l] && ny + dy[m] == y[l]) ok = false; } if(ok){ dp[i | (1<<j) | (1<<k)] = min(dp[i | (1<<j) | (1<<k)],dp[i] + 1); } nx = x[j] - 2; ny = y[j] + 1; ok = true; rep(l,n){ if(j == l) continue; if(k == l) continue; if(i & (1<<l)) continue; if(nx == x[l] && ny == y[l]) ok = false; rep(m,8) if(nx + dx[m] == x[l] && ny + dy[m] == y[l]) ok = false; } if(ok){ dp[i | (1<<j) | (1<<k)] = min(dp[i | (1<<j) | (1<<k)],dp[i] + 1); } } if(x[j] + 2 == x[k] && y[j] == y[k]){ int nx = x[j] + 1,ny = y[j] + 2; bool ok = true; rep(l,n){ if(j == l) continue; if(k == l) continue; if(i & (1<<l)) continue; if(nx == x[l] && ny == y[l]) ok = false; rep(m,8) if(nx + dx[m] == x[l] && ny + dy[m] == y[l]) ok = false; } if(ok){ dp[i | (1<<j) | (1<<k)] = min(dp[i | (1<<j) | (1<<k)],dp[i] + 1); } nx = x[j] + 1; ny = y[j] - 2; ok = true; rep(l,n){ if(j == l) continue; if(k == l) continue; if(i & (1<<l)) continue; if(nx == x[l] && ny == y[l]) ok = false; rep(m,8) if(nx + dx[m] == x[l] && ny + dy[m] == y[l]) ok = false; } if(ok){ dp[i | (1<<j) | (1<<k)] = min(dp[i | (1<<j) | (1<<k)],dp[i] + 1); } } if(x[j] == x[k] && y[j] - 2 == y[k]){ int nx = x[j] + 2,ny = y[j] - 1; bool ok = true; rep(l,n){ if(j == l) continue; if(k == l) continue; if(i & (1<<l)) continue; if(nx == x[l] && ny == y[l]) ok = false; rep(m,8) if(nx + dx[m] == x[l] && ny + dy[m] == y[l]) ok = false; } if(ok){ dp[i | (1<<j) | (1<<k)] = min(dp[i | (1<<j) | (1<<k)],dp[i] + 1); } nx = x[j] - 2; ny = y[j] - 1; ok = true; rep(l,n){ if(j == l) continue; if(k == l) continue; if(i & (1<<l)) continue; if(nx == x[l] && ny == y[l]) ok = false; rep(m,8) if(nx + dx[m] == x[l] && ny + dy[m] == y[l]) ok = false; } if(ok){ dp[i | (1<<j) | (1<<k)] = min(dp[i | (1<<j) | (1<<k)],dp[i] + 1); } } if(x[j] - 2 == x[k] && y[j] == y[k]){ int nx = x[j] - 1,ny = y[j] + 2; bool ok = true; rep(l,n){ if(j == l) continue; if(k == l) continue; if(i & (1<<l)) continue; if(nx == x[l] && ny == y[l]) ok = false; rep(m,8) if(nx + dx[m] == x[l] && ny + dy[m] == y[l]) ok = false; } if(ok){ dp[i | (1<<j) | (1<<k)] = min(dp[i | (1<<j) | (1<<k)],dp[i] + 1); } nx = x[j] - 1; ny = y[j] - 2; ok = true; rep(l,n){ if(j == l) continue; if(k == l) continue; if(i & (1<<l)) continue; if(nx == x[l] && ny == y[l]) ok = false; rep(m,8) if(nx + dx[m] == x[l] && ny + dy[m] == y[l]) ok = false; } if(ok){ dp[i | (1<<j) | (1<<k)] = min(dp[i | (1<<j) | (1<<k)],dp[i] + 1); } } } } } if(dp[(1<<n) - 1] == INF){ assert(false); cout << -1 << endl; } else cout << dp[(1<<n) - 1] << endl; return 0; }