結果
| 問題 | No.1860 Magnets |
| ユーザー |
 Ebishu
|
| 提出日時 | 2022-03-04 21:26:28 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 17,925 bytes |
| コンパイル時間 | 4,047 ms |
| コンパイル使用メモリ | 202,064 KB |
| 最終ジャッジ日時 | 2025-01-28 04:48:14 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 |
コンパイルメッセージ
main.cpp: In member function ‘int BitVector::select(int) const’:
main.cpp:769:9: warning: no return statement in function returning non-void [-Wreturn-type]
769 | }
| ^
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <climits>#include <cmath>#include <complex>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <map>#include <numeric>#include <optional>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <tuple>#include <unordered_map>#include <unordered_set>#include <vector>using namespace std;using lint = long long;using P = pair<lint, lint>;using Pii = pair<int, int>;#define rep(i, n) for (lint i = 0; i < (lint)(n); ++i)#define repe(i, n) for(lint i = 0; i <= (lint)(n); ++i)#define rep1(i, n) for (lint i = 1; i < (lint)(n); ++i)#define rep1e(i, n) for (lint i = 1; i <= (lint)(n); ++i)#define repn(i, a, b) for (lint i = (a); i < (lint)(b); ++i)#define repne(i, a, b) for (lint i = (a); i <= (lint)(b); ++i)#define rrep(i, n) for (lint i = (n); i >= 0; --i)#define all(vec) begin(vec), end(vec)#define rall(vec) rbegin(vec), rend(vec)constexpr long long Mod = /** 1000'000'007LL /*/ 998244353LL /**/;constexpr long long Inf = 1'000'000'000'000'000'010LL;constexpr int IntInf = 1000'000'010;constexpr double Pi = 3.141592653589793238;constexpr double InvPi = 0.318309886183790671;const int di[4] = { 0,1,0,-1 }, dj[4] = { 1,0,-1,0 };#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;using mint = static_modint<Mod>;inline istream& operator>>(istream& is, mint& rhs) {long long tmp;is >> tmp;rhs = tmp;return is;}inline ostream& operator<<(ostream& os, const mint& rhs) { return os << rhs.val(); }mint lagrange_interpolation(const vector<mint>& y, mint t) {const int n = (int)y.size();mint res = 0;vector<mint> inv(n), fact_inv(n);inv[1] = 1;fact_inv[0] = 1;fact_inv[1] = 1;for (int i = 2; i < n; ++i) {inv[i] = -Mod / i * inv[Mod % i];fact_inv[i] = fact_inv[i - 1] * inv[i];}vector<mint> prod2(n);prod2.back() = 1;for (int i = n - 1; i > 0; --i) {prod2[i - 1] = (t - i) * prod2[i];}mint prod1 = 1;for (int i = 0; i < n; ++i) {mint a = y[i];a *= fact_inv[i] * fact_inv[n - 1 - i];if ((n - 1 - i) & 1) a = -a;res += a * prod1 * prod2[i];prod1 *= (t - i);}return res;}template<typename T>lint inversion_number(const vector<T> vec) {vector<T> v = vec;sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());const int n = vec.size();lint res = 0;fenwick_tree<int> b(n);for (int i = 0; i < n; ++i) {const int j = lower_bound(v.begin(), v.end(), vec[i]) - v.begin();res += i - b.sum(0, j);b.add(j, 1);}return res;}// Π(a_i x + b_i)vector<mint> prod(const vector<mint>& a, const vector<mint>& b) {const size_t n = a.size();size_t n1 = 1;while (n1 < n) n1 <<= 1;vector<vector<mint>> fs(2 * n1, { 1 });for (size_t i = n1; i < n + n1; ++i) {fs[i].resize(2);fs[i][0] = b[i - n1];fs[i][1] = a[i - n1];}for (size_t i = n1 - 1; i >= 1; --i) {fs[i] = convolution(fs[i << 1], fs[i << 1 | 1]);}return fs[1];}#endiftemplate<typename T> using prique = priority_queue<T>;template<typename T> using prique_inv = priority_queue<T, vector<T>, greater<T>>;template<typename T> inline istream& operator>>(istream& is, vector<T>& v) { for (auto&& e : v) is >> e; return is; }template<typename T> inline istream& operator>>(istream& is, complex<T>& c) {double real, imag;is >> real >> imag;c.real(real);c.imag(imag);return is;}template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) {for (auto itr = v.begin(), end_itr = v.end(); itr != end_itr;) {os << *itr;if (++itr != end_itr) os << " ";}return os;}template<typename T, typename U> inline bool chmin(T& a, const U b) { return a > b ? a = b, true : false; }template<typename T, typename U> inline bool chmax(T& a, const U b) { return a < b ? a = b, true : false; }template<typename T, typename U> inline istream& operator>>(istream& is, pair<T, U>& rhs) { return is >> rhs.first >> rhs.second; }template<typename T, typename U> inline ostream& operator<<(ostream& os, const pair<T, U>& rhs) { return os << "{" << rhs.first << ", " << rhs.second<< "}"; }template<typename T, typename U, class Pr> inline int getid(const vector<T>& v, const U& value, Pr pred) { return lower_bound(v.begin(), v.end(),value, pred) - v.begin(); }template<typename T, typename U> inline int getid(const vector<T>& v, const U& value) { return getid(v, value, less<>{}); }template<typename T> T gcd(const vector<T>& vec) {T res = vec.front();for (T e : vec) {res = gcd(res, e);if (res == 1) return 1;}return res;}template<typename T> T gcd(initializer_list<T> init) {auto first = init.begin(), last = init.end();T res = *(first++);for (auto itr = first; itr != last; ++itr) {res = gcd(res, *itr);if (res == 1) return 1;}return res;}template<typename T> T lcm(const vector<T>& vec) {T res = vec.front();for (T e : vec) res = lcm(res, e);return res;}template<typename T> T lcm(initializer_list<T> init) {auto first = init.begin(), last = init.end();T res = *(first++);for (auto itr = first; itr != last; ++itr) {res = lcm(res, *itr);}return res;}template<typename T> T pow(T x, lint n) {T res = 1;while (n > 0) {if (n & 1) res *= x;x *= x;n >>= 1;}return res;}inline void YESNO(bool b) { cout << (b ? "YES" : "NO") << "\n"; }inline void YesNo(bool b) { cout << (b ? "Yes" : "No") << "\n"; }inline void yesno(bool b) { cout << (b ? "yes" : "no") << "\n"; }constexpr int bitpopcount(lint 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>T rand(T l, T r) {static mt19937 mt(random_device{}());if constexpr (is_integral_v<T>) {static uniform_int_distribution<T> dist(l, r);return dist(mt);}else if constexpr (is_floating_point_v<T>) {static uniform_real_distribution<T> dist(l, r);return dist(mt);}}bool is_prime(lint x) {for (lint i = 2; i * i <= x; ++i) {if (x % i == 0) return false;}return 1 < x;}vector<lint> divisors(lint n) {vector<lint> res;for (lint x = 1; x * x <= n; ++x) {if (n % x == 0) {res.push_back(x);if (x * x != n) res.push_back(n / x);}}return res;}lint phi(lint n) {lint r = n;for (lint i = 2; i * i <= n; ++i) {if (n % i == 0) {r -= r / i;while (n % i == 0) n /= i;}}if (n > 1) r -= r / n;return r;}lint floor_sqrt(lint n) {lint l = 0, r = 3000'000'000LL;while (r - l > 1) {lint mid = (l + r) / 2;(mid * mid <= n ? l : r) = mid;}return l;}lint ceil_sqrt(lint n) {lint l = 0, r = 3000'000'000LL;while (r - l > 1) {lint mid = (l + r) / 2;(mid * mid < n ? l : r) = mid;}return r;}template<typename T>constexpr bool is_intersect(T l1, T r1, T l2, T r2) {return l1 <= r2 && l2 <= r1;}lint fact[15'000'020], fact_inv[15'000'020], inv[15'000'020];void fact_init(lint n) {fact[0] = fact[1] = 1;fact_inv[0] = fact_inv[1] = 1;inv[1] = 1;for (lint i = 2; i <= n; ++i) {fact[i] = i * fact[i - 1] % Mod;inv[i] = Mod - Mod / i * inv[Mod % i] % Mod;fact_inv[i] = fact_inv[i - 1] * inv[i] % Mod;}}lint modinv(lint a, lint m = Mod) {lint b = m, u = 1, v = 0;while (b != 0) {lint t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}lint modpow(lint x, lint n, lint m = Mod) {if (m == 1) return 0;lint res = 1;x %= m;while (n > 0) {if (n & 1) res = res * x % m;x = x * x % m;n >>= 1;}return res;}lint intpow(lint x, lint n) {lint res = 1;while (n > 0) {if (n & 1) res *= x;x *= x;n >>= 1;}return res;}inline lint comb(lint n, lint r) {if (n < 0 || r < 0 || n < r) return 0;if (r == 0 || r == n) return 1;return fact[n] * fact_inv[n - r] % Mod * fact_inv[r] % Mod;}inline lint perm(lint n, lint r) {if (n < 0 || r < 0 || n < r) return 0;return fact[n] * fact_inv[n - r] % Mod;}template<typename T = int>vector<T> as_vector(const string& str) {vector<T> res(str.size());auto p_res = res.begin();auto p_str = str.begin();auto end_str = str.end();while(p_str != end_str) {*p_res++ = *p_str++ - '0';}return res;}template<typename T>vector<T> compressed(vector<T> v) {sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());return v;}template<typename T>vector<int> compressed_index(vector<T> v) {const int n = v.size();const auto c = compressed(v);vector<int> res(n);for (int i = 0; i < n; ++i) {res[i] = lower_bound(all(c), v[i]) - c.begin();}return res;}// { 値, 個数 }template<typename T>pair<vector<T>, vector<int>> compressed_pair(vector<T> v) {size_t n = v.size();sort(all(v));vector<T> cnt, val;cnt.reserve(n); val.reserve(n);int now_cnt = 1;for (size_t i = 1; i < n; ++i) {if (v[i - 1] != v[i]) {cnt.push_back(now_cnt);val.push_back(v[i - 1]);now_cnt = 1;}else ++now_cnt;}cnt.push_back(now_cnt);val.push_back(v.back());return { val, cnt };}class Factring {private:const lint max_n;vector<lint> sieve;public:explicit Factring(lint max_n): max_n(max_n), sieve(max_n + 1){iota(sieve.begin(), sieve.end(), 0);for (lint i = 2; i * i <= max_n; ++i) {if (sieve[i] < i) continue;for (lint j = i * i; j <= max_n; j += i) {if (sieve[j] == j) sieve[j] = i;}}}unordered_map<lint, lint> calc(lint x) const {unordered_map<lint, lint> res;while (x > 1) {++res[sieve[x]];x /= sieve[x];}return res;}};struct UnionFind {int n;vector<int> par, rank, siz, es;int c;UnionFind() = default;explicit UnionFind(int _n): n(_n), par(_n), rank(_n), siz(_n, 1), es(_n), c(_n){iota(par.begin(), par.end(), 0);}int root(int x) {while (par[x] != x) {x = par[x] = par[par[x]];}return x;}bool same(int x, int y) { return root(x) == root(y); }void unite(int x, int y) {x = root(x); y = root(y);if (x == y) ++es[x];else {c--;if (rank[x] < rank[y]) {par[x] = y;siz[y] += siz[x];es[y] += es[x] + 1;}else {par[y] = x;if (rank[x] == rank[y]) ++rank[x];siz[x] += siz[y];es[x] += es[y] + 1;}}}int count(int x) { return siz[root(x)]; }vector<vector<int>> groups() {vector<int> roots(n), group_size(n);for (int i = 0; i < n; ++i) {roots[i] = root(i);++group_size[roots[i]];}vector<vector<int>> res(n);for (int i = 0; i < n; ++i) {res.reserve(group_size[i]);}for (int i = 0; i < n; ++i) {res[roots[i]].push_back(i);}res.erase(remove_if(res.begin(), res.end(),[](const vector<int>& v) { return v.empty(); }),res.end());return res;}};template<typename T>class CumulativeSum {private:const int n;vector<T> dat;public:CumulativeSum() = default;explicit CumulativeSum(const int n) : n(n), dat(n + 1) {}CumulativeSum(const vector<T>& vec): n(vec.size()), dat(n + 1){for (int i = 0; i < n; ++i) dat[i + 1] = vec[i];}void add(const int i, const T& x) { dat[i + 1] += x; }void build() {for (int i = 0; i < n; ++i) {dat[i + 1] += dat[i];}}// [l, r)T sum(const int l, const int r) const { return dat[r] - dat[l]; }// [0, a)T sum(const int a) const { return dat[a]; }};template<typename T>class CumulativeSum2D {private:vector<vector<T>> dat;public:CumulativeSum2D() = default;explicit CumulativeSum2D(size_t n) : dat(n + 1, vector<T>(n + 1)) {}CumulativeSum2D(size_t h, size_t w) : dat(h + 1, vector<T>(w + 1)) {}CumulativeSum2D(const vector<vector<T>>& vec) {const size_t h = vec.size(), w = vec.front().size();dat.resize(h + 1, vector<T>(w + 1));for (size_t i = 0; i < h; ++i) {for (size_t j = 0; j < w; ++j) {dat[i + 1][j + 1] = dat[i][j + 1] + dat[i + 1][j] - dat[i][j] + vec[i][j];}}}void add(int h, int w, int v) {dat[h + 1][w + 1] += v;}void build() {const size_t h = dat.size() - 1, w = dat.front().size() - 1;for (size_t i = 0; i < h; ++i) {for (size_t j = 0; j < w; ++j) {dat[i + 1][j + 1] = dat[i][j + 1] + dat[i + 1][j] - dat[i][j];}}}// [0, h) × [0, w)T sum(int h, int w) const {return sum(0, 0, h, w);}// [h1, h2) × [w1, w2)T sum(int h1, int w1, int h2, int w2) const {return dat[h2][w2] - dat[h1][w2] - dat[h2][w1] + dat[h1][w1];}};template<typename T>class BinaryIndexedTree {private:const int size;vector<T> dat;public:explicit BinaryIndexedTree(const int size): size(size), dat(size + 1) {}explicit BinaryIndexedTree(const vector<T>& vec): size(vec.size()), dat(size + 1){for (int i = 0; i < size; ++i) dat[i + 1] = vec[i];for (int i = 0; i <= size; ++i) {const int j = i + (i & -i);if (j <= size) dat[j] += dat[i];}}// 0-indexedvoid add(const int a, const T v) {for (int x = a + 1; x <= size; x += (x & -x)) dat[x] += v;}// 0-indexedvoid set(const int a, const T v) {add(a, v - dat[a]);}// [0, a)T sum(const int a) const {T res = 0;for (int x = a; x > 0; x -= x & -x) res += dat[x];return res;}// [a, b)T sum(const int a, const int b) const { return sum(b) - sum(a); }const T& operator[](const size_t x) const { return dat[x + 1]; }};struct Point {lint x, y;Point() = default;constexpr Point(lint x_, lint y_) : x(x_), y(y_) {}constexpr bool operator<(const Point& p) const {if (x != p.x) return x < p.x;return y < p.y;}constexpr Point operator+() const { return *this; }constexpr Point operator-() const { return { -x, -y }; }constexpr Point operator+(const Point& p) const { return { x + p.x, y + p.y }; }constexpr Point operator-(const Point& p) const { return { x - p.x, y - p.y }; }constexpr Point operator*(lint s) const { return { x * s, y * s }; }constexpr Point& operator+=(const Point& p) {x += p.x; y += p.y;return *this;}constexpr Point& operator-=(const Point& p) {x -= p.x; y -= p.y;return *this;}constexpr lint dot(const Point& p) const { return x * p.x + y * p.y; }constexpr lint cross(const Point& p) const { return x * p.y - y * p.x; }constexpr lint lengthSq() const { return x * x + y * y; }double length() const { return hypot(x, y); }constexpr lint distanceSq(const Point& p) const { return (*this - p).lengthSq(); }double distance(const Point& p) const { return (*this - p).length(); }friend constexpr Point operator*(lint s, const Point& p) { return p * s; }friend istream& operator>>(istream& is, Point& p) { return is >> p.x >> p.y; }};template<typename T, typename U>T nearest_value(const vector<T>& v, const U& value) {auto itr = lower_bound(v.begin(), v.end(), value);if (itr == v.begin()) return *itr;if (itr == v.end()) return *prev(itr);return min(*itr - value, value - *prev(itr)) + value;}class BitVector {public:using u8 = uint8_t;using u16 = uint16_t;int n, l;static constexpr int small_per_large = 32;static constexpr int large_size = 256, small_size = 8;vector<u8> bit;vector<u16> large;vector<vector<u8>> small;static inline const vector<u8> table = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,};explicit BitVector(int _n): n(_n), l((_n + large_size - 1) / large_size){bit.assign(l * small_per_large, 0);large.assign(l + 1, 0);small.assign(l, vector<u8>(small_per_large, 0));}explicit BitVector(vector<bool> vec): n(vec.size()), l((n + large_size - 1) / large_size){bit.resize(l * small_per_large);large.assign(l + 1, 0);small.assign(l, vector<u8>(small_per_large, 0));for (int i = 0; i < n; ++i) set(i, vec[i]);}void set(int p, bool b) {const int bp = p >> 8;const int a = p & 7;if (b) bit[bp] |= 1 << a;else bit[bp] &= ~(1 << a);}bool get(int p) const {const int bp = p >> 8;const int a = p & 7;return bit[bp] >> a & 1;}void build() {large[0] = 0;for (int i = 0; i < l; ++i) {small[i][0] = 0;for (int j = 0; j < small_per_large - 1; ++j) {small[i][j + 1] = small[i][j] + table[bit[small_per_large * i + j]];}large[i + 1] = large[i] + small[i][small_per_large - 1] + table[bit[small_per_large * i + small_per_large - 1]];}}// [0, p)int rank(int p) const {const int lp = p >> 8;const int sp = (p & 255) >> 3;const int a = p & 7;const int rem = bit[p >> 3] & ((1 << a) - 1);return large[lp] + small[lp][sp] + table[rem];}int select(int n) const {// todo}};int main() {lint a, b;cin >> a >> b;if (a > b) swap(a, b);int d = b - a, ans = 2 * a;if (d <= 1) ans += d;else {ans += 1;d -= 1;ans += 2 * d;}cout << ans << endl;}