結果

問題 No.1298 OR XOR
ユーザー Cyanmond
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

//#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 ACL
public:
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 endregion
using 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0