結果
問題 | No.911 ラッキーソート |
ユーザー |
![]() |
提出日時 | 2019-10-19 00:35:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 179 ms / 2,000 ms |
コード長 | 4,158 bytes |
コンパイル時間 | 1,989 ms |
コンパイル使用メモリ | 176,708 KB |
実行使用メモリ | 5,888 KB |
最終ジャッジ日時 | 2024-06-25 20:27:59 |
合計ジャッジ時間 | 7,878 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
/*** code generated by JHelper* More info: https://github.com/AlexeyDmitriev/JHelper* @author*/#include <iostream>#include <fstream>#ifndef SOLUTION_COMMON_H#include <bits/stdc++.h>using namespace std;using ll = long long;using PI = pair<int, int>;template<class T> using V = vector<T>;using VI = V<int>;#define _1 first#define _2 second#ifdef MY_DEBUG# define DEBUG(x) x#else# define DEBUG(x)#endiftemplate<class T>inline void debug(T &A) {DEBUG(for (const auto &a : A) {cerr << a << " ";}cerr << '\n';)}template<class T, class Func>inline void debug_with_format(T &A, Func f) {DEBUG(for (const auto &a : A) {cerr << f(a) << " ";}cerr << '\n';)}template<class T>inline void debug_dim2(T &A) {DEBUG(for (const auto &as : A) {debug(as);})}template<typename ... Args>inline void debug(const char *format, Args const &... args) {DEBUG(fprintf(stderr, format, args ...);cerr << '\n';)}template<typename ... Args>string format(const string &fmt, Args ... args) {size_t len = snprintf(nullptr, 0, fmt.c_str(), args ...);vector<char> buf(len + 1);snprintf(&buf[0], len + 1, fmt.c_str(), args ...);return string(&buf[0], &buf[0] + len);}template<class T1, class T2>string fmtP(pair<T1, T2> a) {stringstream ss;ss << "(" << a._1 << "," << a._2 << ")";return ss.str();}#define SOLUTION_COMMON_H#endif //SOLUTION_COMMON_Hconst int MOD = 1000000007;class D {public:ll calc(VI &bit, ll l, ll r) {V<V<V<ll>>> memo(61, V<V<ll>>(2, V<ll>(2, -1)));function<ll(int, int, int)> dfs = [&](int k, int more, int less) {if (k == -1) return 1ll;if (memo[k][more][less] != -1) return memo[k][more][less];ll res = 0ll;for (int i = 0; i < 2; ++i) {if (!(bit[k] == i || bit[k] == 2)) continue;if (i == 0 && !more && (l >> k & 1)) continue;if (i == 1 && !less && !(r >> k & 1)) continue;int nmore = more || !(l >> k & 1) && i == 1;int nless = less || (r >> k & 1) && i == 0;res += dfs(k - 1, nmore, nless);}memo[k][more][less] = res;return res;};return dfs(60, 0, 0);}void solve(std::istream& in, std::ostream& out) {int n;ll l, r;in >> n >> l >> r;V<ll> a(n);for (int i = 0; i < n; ++i) {in >> a[i];}VI g(n);int id = 1;auto mergeTpe = [](int t1, int t2) {if (t1 == 2 && t2 == 3 || t1 == 3 && t2 == 2) return -1;if (t1 == 0 || t1 == 1) return t2;return t1;};VI bit(61);for (int k = 60; k >= 0; --k) {int tpe = 0; // 0: 0000, 1: 1111, 2: 0011, 3: 1100int cur = 0;int curG = -1;for (int i = 0; i < n; ++i) {// グループが変わったif (curG != g[i]) {tpe = mergeTpe(tpe, cur);if (tpe == -1) {out << 0;return;}cur = (a[i] >> k & 1) == 1 ? 1 : 0;curG = g[i];continue;}if (cur == 0 && (a[i] >> k & 1) == 1) {debug("enter(2) %d %d", k, i);cur = 2;g[i] = id++;continue;}if (cur == 1 && (a[i] >> k & 1) == 0) {debug("enter(3) %d %d", k, i);cur = 3;g[i] = id++;continue;}if (cur == 2 && (a[i] >> k & 1) == 0) {out << 0;return;}if (cur == 3 && (a[i] >> k & 1) == 1) {out << 0;return;}if (cur == 2 || cur == 3) {g[i] = g[i - 1];}}tpe = mergeTpe(tpe, cur);if (tpe == -1) {out << 0;return;}if (tpe == 0 || tpe == 1) {bit[k] = 2;} else if (tpe == 2) {bit[k] = 0;} else {bit[k] = 1;}debug(g);}debug(bit);out << calc(bit, l, r);}};int main() {D solver;std::istream& in(std::cin);std::ostream& out(std::cout);solver.solve(in, out);return 0;}