結果

問題 No.911 ラッキーソート
ユーザー yakamoto
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

/**
* 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)
#endif
template<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_H
const 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: 1100
int 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0