結果
問題 | No.1900 Don't be Powers of 2 |
ユーザー |
👑 |
提出日時 | 2022-04-08 21:32:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 2,980 bytes |
コンパイル時間 | 1,193 ms |
コンパイル使用メモリ | 103,392 KB |
実行使用メモリ | 15,488 KB |
最終ジャッジ日時 | 2024-11-28 12:08:31 |
合計ジャッジ時間 | 2,395 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <cassert> #include <cmath> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using Int = long long; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } namespace BM { constexpr int LIM_N0 = 2010; constexpr int LIM_N1 = 2010; constexpr int LIM_M = 1'000'010; int n0, n1, m, as[LIM_M], bs[LIM_M]; int to[LIM_N0], fr[LIM_N1], tof; int pt[LIM_N0 + 2], zu[LIM_M], used[LIM_N0], lev[LIM_N0], que[LIM_N0], *qb, *qe; void init(int n0_, int n1_) { n0 = n0_; n1 = n1_; m = 0; } int ae(int u, int v) { as[m] = u; bs[m] = v; return m++; } int augment(int u) { used[u] = tof; for (int j = pt[u]; j < pt[u + 1]; ++j) { const int v = zu[j]; const int w = fr[v]; if (!~w || (used[w] != tof && lev[u] < lev[w] && augment(w))) { to[u] = v; fr[v] = u; return 1; } } return 0; } int run() { memset(pt, 0, (n0 + 2) * sizeof(int)); for (int i = 0; i < m; ++i) ++pt[as[i] + 2]; for (int u = 2; u <= n0; ++u) pt[u + 1] += pt[u]; for (int i = 0; i < m; ++i) zu[pt[as[i] + 1]++] = bs[i]; memset(to, ~0, n0 * sizeof(int)); memset(fr, ~0, n1 * sizeof(int)); memset(used, ~0, n0 * sizeof(int)); for (tof = 0; ; ) { qb = qe = que; memset(lev, ~0, n0 * sizeof(int)); for (int u = 0; u < n0; ++u) if (!~to[u]) lev[*qe++ = u] = 0; for (; qb != qe; ) { const int u = *qb++; for (int j = pt[u]; j < pt[u + 1]; ++j) { const int w = fr[zu[j]]; if (~w && !~lev[w]) lev[*qe++ = w] = lev[u] + 1; } } int f = 0; for (int u = 0; u < n0; ++u) if (!~to[u]) f += augment(u); if (!f) return tof; tof += f; } } } // namespace BM int N; vector<int> A; int main() { for (; ~scanf("%d", &N); ) { A.resize(N); for (int i = 0; i < N; ++i) { scanf("%d", &A[i]); } vector<int> iss[2]; for (int i = 0; i < N; ++i) { iss[__builtin_parity(A[i])].push_back(i); } const int n0 = iss[0].size(); const int n1 = iss[1].size(); BM::init(n0, n1); for (int u = 0; u < n0; ++u) for (int v = 0; v < n1; ++v) { const int b = A[iss[0][u]] ^ A[iss[1][v]]; if (!(b & (b - 1))) { BM::ae(u, v); } } const int res = BM::run(); printf("%d\n", N - res); } return 0; }