結果
問題 | No.1298 OR XOR |
ユーザー |
|
提出日時 | 2020-11-27 23:42:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 9,044 bytes |
コンパイル時間 | 9,905 ms |
コンパイル使用メモリ | 429,992 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-26 19:38:22 |
合計ジャッジ時間 | 11,141 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
//#pragma GCC target ("avx")//#pragma GCC optimize("O3")//#pragma GCC optimize("unroll-loops")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#include "bits/stdc++.h"#pragma region library#ifndef _MSC_FULL_VER// Only AtCoder and AOJ#include <boost/multiprecision/cpp_dec_float.hpp>#include <boost/multiprecision/cpp_int.hpp>#include <boost/range/algorithm.hpp>#include <boost/range/irange.hpp>using boost::irange;using biglong = boost::multiprecision::cpp_int;using smalldouble = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1024>>;#define debug(x) void(0)using lint = long long;using Lint = long long;using Int = int;constexpr int dx[] = { 1, 0, -1, 0 };constexpr int dy[] = { 0, 1, 0, -1 };constexpr int INF = INT_MAX / 2;constexpr long long LINF = INT64_MAX / 2ll;constexpr int mod = 1000000007;constexpr int mod2 = 998244353;constexpr double eps = DBL_EPSILON;template <class T>using prique = std::priority_queue<T, std::vector<T>, std::greater<T>>;#define codeinit std::ios::sync_with_stdio(false); std::cin.tie(0)#define decimalinit std::cout << std::fixed << std::setprecision(15)inline int read() {int S; std::cin >> S;return S;}inline long long readll() {long long S; std::cin >> S;return S;}inline std::string reads() {std::string S; std::cin >> S;return S;}template <class T, class U>inline bool ckmax(T& A, const U& B) {return B > A ? A = B, true : false;}template <class T, class U>inline bool ckmin(T& A, const U& B) {return B < A ? A = B, true : false;}template <class T, class U>inline T Pow(T A, U B) {T res(1);while (B) {if (B & 1) res *= A;A *= A;B >>= 1;}return res;}inline long long gcd(long long A, long long B) {while (B) {const long long C = A;A = B; B = C % B;}return A;}inline long long lcm(const long long A, const long long B) {return A / gcd(A, B) * B;}inline long long modpow(long long A, long long B, const long long MOD) {long long res(1);while (B) {if (B & 1) res *= A, res %= MOD;A *= A; A %= MOD;B >>= 1;}return res;}template <class T>inline T inverse(T A, const T M) {T B = M, U = 1, V = 0;while (B) {T t = A / B;A -= t * B; std::swap(A, B);U -= t * V; std::swap(U, V);}U %= M;return U < 0 ? U += M, U : U;}inline long long modlog(long long a, long long b, long long m) { // return x(a ^ x ≡ b(mod m))a %= m, b %= m;long long k = 1, add = 0, g;while ((g = gcd(a, m)) > 1) {if (b == k) return add;if (b % g) return -1;b /= g, m /= g, ++add;k = (k * a / g) % m;}int n = (int)sqrt(m) + 1;long long an = modpow(a, n, m);std::unordered_map<long long, long long> vals;for (long long q = 0, cur = b; q <= n; ++q) {vals[cur] = q;cur = (cur * a) % m;}for (long long p = 1, cur = k; p <= n; ++p) {cur = (cur * an) % m;if (vals.count(cur)) {long long ans = n * p - vals[cur] + add;return ans;}}return -1;}constexpr int ckmodMod = mod;template<class T>inline void ckmod(T& A) {A %= ckmodMod;if (A < 0) A += ckmodMod;return;}std::vector<bool> IsPrime;inline void sieve(size_t max) {if (max + 1 > IsPrime.size()) {IsPrime.resize(max + 1, true);}IsPrime[0] = false;IsPrime[1] = false;for (size_t i = 2; i * i <= max; ++i) {if (IsPrime[i]) {for (size_t j = 2; i * j <= max; ++j) {IsPrime[i * j] = false;}}}return;}constexpr int COMMAX = 510000;constexpr int COMMOD = 1000000007;long long COMfac[COMMAX], COMfinv[COMMAX], COMinv[COMMAX];void COMinit() {COMfac[0] = COMfac[1] = 1;COMfinv[0] = COMfinv[1] = 1;COMinv[1] = 1;for (int i = 2; i < COMMAX; i++) {COMfac[i] = COMfac[i - 1] * i % COMMOD;COMinv[i] = COMMOD - COMinv[COMMOD % i] * (COMMOD / i) % COMMOD;COMfinv[i] = COMfinv[i - 1] * COMinv[i] % COMMOD;}}inline long long com(int n, int k) {if (n < k) return 0;if (n < 0 || k < 0) return 0;return COMfac[n] * (COMfinv[k] * COMfinv[n - k] % COMMOD) % COMMOD;}inline bool isprime(long long N) {if (N == 1) return false;for (long long i = 2; i * i <= N; i++) {if (N % i == 0) return false;}return true;}std::vector<std::pair<long long, long long>> prime_fact(long long N) {std::vector<std::pair<long long, long long>> res;for (long long i = 2; i * i <= N; i++) {if (N % i != 0) continue;long long cnt = 0;while (N % i == 0) {++cnt;N /= i;}res.push_back({ i, cnt });}if (N != 1) res.push_back({ N, 1 });return res;}class UnionFind {public:UnionFind() : _n(0) {}UnionFind(int n) : _n(n), parent_or_size(n, -1) {}int merge(int a, int b) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);int x = leader(a), y = leader(b);if (x == y) return x;if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);parent_or_size[x] += parent_or_size[y];parent_or_size[y] = x;return x;}bool same(int a, int b) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);return leader(a) == leader(b);}int leader(int a) {assert(0 <= a && a < _n);if (parent_or_size[a] < 0) return a;return parent_or_size[a] = leader(parent_or_size[a]);}int size(int a) {assert(0 <= a && a < _n);return -parent_or_size[leader(a)];}std::vector<std::vector<int>> groups() {std::vector<int> leader_buf(_n), group_size(_n);for (int i = 0; i < _n; i++) {leader_buf[i] = leader(i);group_size[leader_buf[i]]++;}std::vector<std::vector<int>> result(_n);for (int i = 0; i < _n; i++) {result[i].reserve(group_size[i]);}for (int i = 0; i < _n; i++) {result[leader_buf[i]].push_back(i);}result.erase(std::remove_if(result.begin(), result.end(),[&](const std::vector<int>& v) { return v.empty(); }),result.end());return result;}private:int _n;std::vector<int> parent_or_size;};struct KruskalEdgestruct {int u;int v;long long cost;bool operator<(const KruskalEdgestruct& e) const { return this->cost < e.cost; }};class Kruskal {public:long long sum;private:UnionFind UF;std::vector<KruskalEdgestruct> edges;int V;//vector<long long> result;//vector<vector<KruskalEdgestruct>> graph;public:Kruskal(const std::vector<KruskalEdgestruct>& edges_, int V_) : edges(edges_), V(V_) { init(); }private:void init() {sort(edges.begin(), edges.end());UF = UnionFind(V);sum = 0;for (auto& e : edges) {if (!UF.same(e.u, e.v)) {UF.merge(e.u, e.v);sum += e.cost;}}}};int ceil_pow2(int n) {int x = 0;while ((1U << x) < (unsigned int)(n)) x++;return x;}template <class S, S(*op)(S, S), S(*e)()>class segtree { // Segmenttree by ACLpublic:segtree() : segtree(0) {}segtree(int n) : segtree(std::vector<S>(n, e())) {}segtree(const std::vector<S>& v) : _n(int(v.size())) {log = ceil_pow2(_n);//size = 1 << log;d = std::vector<S>(2 * size, e());for (int i = 0; i < _n; i++) d[size + i] = v[i];for (int i = size - 1; i >= 1; i--) {update(i);}}void set(int p, S x) {assert(0 <= p && p < _n);p += size;d[p] = x;for (int i = 1; i <= log; i++) update(p >> i);}S get(int p) {assert(0 <= p && p < _n);return d[p + size];}S prod(int l, int r) {assert(0 <= l && l <= r && r <= _n);S sml = e(), smr = e();l += size;r += size;while (l < r) {if (l & 1) sml = op(sml, d[l++]);if (r & 1) smr = op(d[--r], smr);l >>= 1;r >>= 1;}return op(sml, smr);}S all_prod() { return d[1]; }template <bool (*f)(S)> int max_right(int l) {return max_right(l, [](S x) { return f(x); });}template <class F> int max_right(int l, F f) {assert(0 <= l && l <= _n);assert(f(e()));if (l == _n) return _n;l += size;S sm = e();do {while (l % 2 == 0) l >>= 1;if (!f(op(sm, d[l]))) {while (l < size) {l = (2 * l);if (f(op(sm, d[l]))) {sm = op(sm, d[l]);l++;}}return l - size;}sm = op(sm, d[l]);l++;} while ((l & -l) != l);return _n;}template <bool (*f)(S)> int min_left(int r) {return min_left(r, [](S x) { return f(x); });}template <class F> int min_left(int r, F f) {assert(0 <= r && r <= _n);assert(f(e()));if (r == 0) return 0;r += size;S sm = e();do {r--;while (r > 1 && (r % 2)) r >>= 1;if (!f(op(d[r], sm))) {while (r < size) {r = (2 * r + 1);if (f(op(d[r], sm))) {sm = op(d[r], sm);r--;}}return r + 1 - size;}sm = op(d[r], sm);} while ((r & -r) != r);return 0;}private:int _n, size, log;std::vector<S> d;void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }};#else# include <intrin.h># define __builtin_popcount __popcnt#endif#pragma endregionusing namespace std;/* -------- I want to be "Bluemond"! -------- */int32_t main(void) {int n = read();if (__builtin_popcount(n) == 1) cout << -1 << ' ' << -1 << ' ' << -1 << endl;else cout << n << ' ' << (n & -n) << ' ' << (n xor (n & -n)) << endl;return 0;}