結果
問題 | No.1228 I hate XOR Matching |
ユーザー | tran0826 |
提出日時 | 2020-09-13 02:47:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 10,607 bytes |
コンパイル時間 | 1,768 ms |
コンパイル使用メモリ | 155,608 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-10 19:40:34 |
合計ジャッジ時間 | 5,875 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 1 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 1 ms
5,376 KB |
testcase_32 | AC | 1 ms
5,376 KB |
testcase_33 | AC | 2 ms
5,376 KB |
testcase_34 | AC | 2 ms
5,376 KB |
ソースコード
#include<iostream>#include<vector>#include<set>#include<queue>#include<map>#include<algorithm>#include<cstring>#include<string>#include<cassert>#include<cmath>#include<climits>#include<iomanip>#include<stack>#include<unordered_map>#include<bitset>#include<limits>#include<complex>#include<array>#include<numeric>#include<functional>#include<random>using namespace std;#define ll long long#define ull unsigned long long#define rep(i,m,n) for(ll (i)=(ll)(m);i<(ll)(n);i++)#define REP(i,n) rep(i,0,n)#define all(hoge) (hoge).begin(),(hoge).end()typedef pair<ll, ll> P;constexpr long double m_pi = 3.1415926535897932L;constexpr ll MOD = 1000000007;constexpr ll INF = 1LL << 61;constexpr long double EPS = 1e-10;template<typename T> using vector2 = vector<vector<T>>;template<typename T> using vector3 = vector<vector2<T>>;typedef vector<ll> Array;typedef vector<Array> Matrix;string operator*(const string& s, int k) {if (k == 0) return "";string p = (s + s) * (k / 2);if (k % 2 == 1) p += s;return p;}template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }struct Edge {//グラフint to, rev; ll cap;Edge(int _to, ll _cap, int _rev) {to = _to; cap = _cap; rev = _rev;}};typedef vector<Edge> Edges;typedef vector<Edges> Graph;void add_edge(Graph& G, int from, int to, ll cap, bool revFlag, ll revCap) {//最大フロー求める Ford-fulkersonG[from].push_back(Edge(to, cap, (ll)G[to].size() + (from == to)));if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));//最小カットの場合逆辺は0にする}ll max_flow_dfs(Graph& G, ll v, ll t, ll f, vector<bool>& used){if (v == t)return f;used[v] = true;for (int i = 0; i < G[v].size(); ++i) {Edge& e = G[v][i];if (!used[e.to] && e.cap > 0) {ll d = max_flow_dfs(G, e.to, t, min(f, e.cap), used);if (d > 0) {e.cap -= d;G[e.to][e.rev].cap += d;return d;}}}return 0;}//二分グラフの最大マッチングを求めたりも出来る また二部グラフの最大独立集合は頂点数-最大マッチングのサイズll max_flow(Graph& G, ll s, ll t)//O(V(V+E)){ll flow = 0;for (;;) {vector<bool> used(G.size());REP(i, used.size())used[i] = false;ll f = max_flow_dfs(G, s, t, INF, used);if (f == 0) {return flow;}flow += f;}}void BellmanFord(Graph& G, ll s, Array& d, Array& negative) {//O(|E||V|)d.resize(G.size());negative.resize(G.size());REP(i, d.size())d[i] = INF;REP(i, d.size())negative[i] = false;d[s] = 0;REP(k, G.size() - 1) {REP(i, G.size()) {REP(j, G[i].size()) {if (d[i] != INF && d[G[i][j].to] > d[i] + G[i][j].cap) {d[G[i][j].to] = d[i] + G[i][j].cap;}}}}REP(k, G.size() - 1) {REP(i, G.size()) {REP(j, G[i].size()) {if (d[i] != INF && d[G[i][j].to] > d[i] + G[i][j].cap) {d[G[i][j].to] = d[i] + G[i][j].cap;negative[G[i][j].to] = true;}if (negative[i] == true)negative[G[i][j].to] = true;}}}}void Dijkstra(Graph& G, ll s, Array& d) {//O(|E|log|V|)d.resize(G.size());REP(i, d.size())d[i] = INF;d[s] = 0;priority_queue<P, vector<P>, greater<P>> q;q.push(make_pair(0, s));while (!q.empty()) {P a = q.top();q.pop();if (d[a.second] < a.first)continue;REP(i, G[a.second].size()) {Edge e = G[a.second][i];if (d[e.to] > d[a.second] + e.cap) {d[e.to] = d[a.second] + e.cap;q.push(make_pair(d[e.to], e.to));}}}}void WarshallFloyd(Graph& G, Matrix& d) {//O(V^3)d.resize(G.size());REP(i, d.size())d[i].resize(G.size());REP(i, d.size()) {REP(j, d[i].size()) {d[i][j] = ((i != j) ? INF : 0);}}REP(i, G.size()) {REP(j, G[i].size()) {chmin(d[i][G[i][j].to], G[i][j].cap);}}REP(i, G.size()) {REP(j, G.size()) {REP(k, G.size()) {if (d[j][i] != INF && d[i][k] != INF)chmin(d[j][k], d[j][i] + d[i][k]);}}}}bool tsort(Graph& graph, vector<int>& order) {//トポロジカルソートO(E+V)int n = graph.size(), k = 0;vector<int> in(n);for (auto& es : graph)for (auto& e : es)in[e.to]++;priority_queue<int, vector<int>, greater<int>> que;REP(i, n)if (in[i] == 0)que.push(i);while (que.size()) {int v = que.top();que.pop();order.push_back(v);for (auto& e : graph[v])if (--in[e.to] == 0)que.push(e.to);}if (order.size() != n)return false;else return true;}class Lca {public:const int n = 0;const int log2_n = 0;std::vector<std::vector<int>> parent;std::vector<int> depth;Lca() {}Lca(const Graph& g, int root): n(g.size()), log2_n(log2(n) + 1), parent(log2_n, std::vector<int>(n)), depth(n) {dfs(g, root, -1, 0);for (int k = 0; k + 1 < log2_n; k++) {for (int v = 0; v < (int)g.size(); v++) {if (parent[k][v] < 0)parent[k + 1][v] = -1;elseparent[k + 1][v] = parent[k][parent[k][v]];}}}void dfs(const Graph& g, int v, int p, int d) {parent[0][v] = p;depth[v] = d;for (auto& e : g[v]) {if (e.to != p) dfs(g, e.to, v, d + 1);}}int get(int u, int v) {if (depth[u] > depth[v]) std::swap(u, v);for (int k = 0; k < log2_n; k++) {if ((depth[v] - depth[u]) >> k & 1) {v = parent[k][v];}}if (u == v) return u;for (int k = log2_n - 1; k >= 0; k--) {if (parent[k][u] != parent[k][v]) {u = parent[k][u];v = parent[k][v];}}return parent[0][u];}};class UnionFind {vector<int> data;int n;public:UnionFind(int size) : data(size, -1), n(size) { }bool merge(int x, int y) {//xとyの集合を統合するx = root(x); y = root(y);if (x != y) {if (data[y] < data[x]) swap(x, y);data[x] += data[y]; data[y] = x;}n -= (x != y);return x != y;}bool same(int x, int y) {//xとyが同じ集合か返すreturn root(x) == root(y);}int root(int x) {//xのルートを返すreturn data[x] < 0 ? x : data[x] = root(data[x]);}int size(int x) {//xの集合のサイズを返すreturn -data[root(x)];}int num() {//集合の数を返すreturn n;}};template<typename T, typename F>class SegmentTree {private:T identity;F merge;ll n;vector<T> dat;public:SegmentTree(F f, T id, vector<T> v) :merge(f), identity(id) {int _n = v.size();n = 1;while (n < _n)n *= 2;dat.resize(2 * n - 1, identity);REP(i, _n)dat[n + i - 1] = v[i];for (int i = n - 2; i >= 0; i--)dat[i] = merge(dat[i * 2 + 1], dat[i * 2 + 2]);}SegmentTree(F f, T id, int _n) :merge(f), identity(id) {n = 1;while (n < _n)n *= 2;dat.resize(2 * n - 1, identity);}void set_val(int i, T x) {i += n - 1;dat[i] = x;while (i > 0) {i = (i - 1) / 2;dat[i] = merge(dat[i * 2 + 1], dat[i * 2 + 2]);}}T query(int l, int r) {T left = identity, right = identity;l += n - 1; r += n - 1;while (l < r) {if ((l & 1) == 0)left = merge(left, dat[l]);if ((r & 1) == 0)right = merge(dat[r - 1], right);l = l / 2;r = (r - 1) / 2;}return merge(left, right);}};template< typename T >class FenwickTree {vector< T > data;int n;int p;public:FenwickTree(int n) :n(n) {data.resize(n + 1LL, 0);p = 1;while (p < data.size())p *= 2;}T sum(int k) {T ret = 0;for (; k > 0; k -= k & -k) ret += data[k];return (ret);}T sum(int a, int b) { return sum(b) - sum(a); }//[a,b)void add(int k, T x) {for (++k; k <= n; k += k & -k) data[k] += x;}int lower_bound(ll w) {if (w <= 0)return -1;int x = 0;for (int k = p / 2; k > 0; k /= 2) {if (x + k <= n && data[x + k] < w)w -= data[x + k], x += k;}return x;}};//約数求める //約数void divisor(ll n, vector<ll>& ret) {for (ll i = 1; i * i <= n; i++) {if (n % i == 0) {ret.push_back(i);if (i * i != n) ret.push_back(n / i);}}sort(ret.begin(), ret.end());}void prime_factorization(ll n, vector<P>& ret) {for (ll i = 2; i * i <= n; i++) {if (n % i == 0) {ret.push_back({ i,0 });while (n % i == 0) {n /= i;ret[ret.size() - 1].second++;}}}if (n != 1)ret.push_back({ n,1 });}inline ll mod_pow(ll x, ll n, ll mod) {ll res = 1;while (n > 0) {if (n & 1) res = res * x % mod;x = x * x % mod;n >>= 1;}return res;}inline ll mod_inv(ll x, ll mod) {return mod_pow(x, mod - 2, mod);}class Combination {public:Array fact;Array fact_inv;ll mod;//if n >= mod use lucasll nCr(ll n, ll r) {if (n < r)return 0;if (n < mod)return ((fact[n] * fact_inv[r] % mod) * fact_inv[n - r]) % mod;ll ret = 1;while (n || r) {ll _n = n % mod, _r = r % mod;n /= mod; r /= mod;(ret *= nCr(_n, _r)) %= mod;}return ret;}ll nPr(ll n, ll r) {return (fact[n] * fact_inv[n - r]) % mod;}ll nHr(ll n, ll r) {return nCr(r + n - 1, r);}Combination(ll _n, ll _mod) {mod = _mod;ll n = min(_n + 1, mod);fact.resize(n);fact[0] = 1;REP(i, n - 1) {fact[i + 1] = (fact[i] * (i + 1LL)) % mod;}fact_inv.resize(n);fact_inv[n - 1] = mod_inv(fact[n - 1], mod);for (int i = n - 1; i > 0; i--) {fact_inv[i - 1] = fact_inv[i] * i % mod;}}};ll popcount(ll x) {x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);x = (x & 0x0F0F0F0F0F0F0F0F) + (x >> 4 & 0x0F0F0F0F0F0F0F0F);x = (x & 0x00FF00FF00FF00FF) + (x >> 8 & 0x00FF00FF00FF00FF);x = (x & 0x0000FFFF0000FFFF) + (x >> 16 & 0x0000FFFF0000FFFF);x = (x & 0x00000000FFFFFFFF) + (x >> 32 & 0x00000000FFFFFFFF);return x;}template<typename T>void rowReduction(vector<T> mat, vector<T>& basis) {//掃き出し法for (auto e : mat) {for (auto b : basis)chmin(e, e ^ b);if (e)basis.push_back(e);}sort(all(basis), greater<T>());}int main() {ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);ll k, x;cin >> k >> x;if (x == 0) {if (k != 0)k--;else k++;cout << "Yes\n1" << "\n";cout << k << "\n";return 0;}else if (k == 0) x++;if (popcount(x) != 1) {cout << "No" << "\n";return 0;}ll cnt = 0;while (x != 1)cnt++, x >>= 1;Array ans;ans.push_back(k);if (cnt != 0) {REP(i, 5)ans.push_back(1 << i);if (k < 32)cnt--;rep(i, 1, 32) {if (cnt == 0)break;if (i == k)continue;ans.push_back(i);cnt--;}}cout << "Yes" << "\n";cout << ans.size() << "\n";REP(i, ans.size())cout << ans[i] << " ";cout << endl;return 0;}