結果
問題 | No.911 ラッキーソート |
ユーザー |
![]() |
提出日時 | 2019-10-18 22:45:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 3,585 bytes |
コンパイル時間 | 1,522 ms |
コンパイル使用メモリ | 171,540 KB |
実行使用メモリ | 7,792 KB |
最終ジャッジ日時 | 2024-06-25 17:52:48 |
合計ジャッジ時間 | 4,610 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
// #define DEBUGGING#include <bits/stdc++.h>using namespace std;#define endl '\n'#define ALL(V) (V).begin(), (V).end()#define ALLR(V) (V).rbegin(), (V).rend()template <typename T> using V = vector<T>;template <typename T> using VV = V<V<T>>;using ll = int64_t;using ull = uint64_t;using PLL = pair<ll, ll>;template <typename T> const T& var_min(const T &t) { return t; }template <typename T> const T& var_max(const T &t) { return t; }template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); }template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); }template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); }template <typename T> void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); }namespace init__ {struct InitIO {InitIO() {cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << fixed << setprecision(30);}} init_io;}#ifdef DEBUGGING// #include "../debug/debug.cpp"#include "../../debug/debug.cpp"#else#define DEBUG(...) 0#define DEBUG_SEPARATOR_LINE 0#endiftemplate <typename T>T make_v(T init) { return init; }template <typename T, typename... Tail>auto make_v(T init, size_t s, Tail... tail) {#define rec make_v(init, tail...)return V<decltype(rec)>(s, rec);#undef rec}ll solve() {ll N, L, R;cin >> N >> L >> R;V<ll> A(N);for(auto &&ele : A) cin >> ele;V<ll> must, must_not;for(ll i = 0; i < N - 1; i++) {ll x = A[i], y = A[i + 1];if(x == y) return 0;for(ll b = 61; 0 <= b; b--) {if(((x >> b) ^ (y >> b)) & 1) {(x < y ? must_not : must).push_back(b);break;}}}DEBUG(must, must_not);V<ll> status(64);for(ll m : must) status[m] = 1;for(ll m : must_not) {if(status[m] == 1) return 0;status[m] = -1;}ll up = 1, low = 1, ok = 0;ll msb_b = 61;while(((R >> msb_b) & 1) == 0) msb_b--;ll b = msb_b;while(0 <= b) {ll br = (R >> b) & 1;ll bl = (L >> b) & 1;if(br != bl) {if(status[b] == 1) low = 0;if(status[b] == -1) up = 0;break;}DEBUG(make_tuple(b, br, bl));if(status[b] == 1 && br == 0) return 0;if(status[b] == -1 && br == 1) return 0;b--;}if(b == -1) return 1;ll init_b = b;DEBUG(status, init_b);for(ll b = init_b - 1; 0 <= b; b--) {ll br = (R >> b) & 1;ll bl = (L >> b) & 1;if(status[b] == 0) {ok *= 2;if(br) ok += up;if(!bl) ok += low;} else if(status[b] == 1) {if(!br) {// ok += up;up = 0;}if(!bl) {ok += low;low = 0;}} else if(status[b] == -1) {if(br) {ok += up;up = 0;}if(bl) {// ok += low;low = 0;}}}return ok + up + low;}int main() {cout << solve() << endl;return 0;}