結果
問題 | No.911 ラッキーソート |
ユーザー |
![]() |
提出日時 | 2019-10-19 13:22:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 224 ms / 2,000 ms |
コード長 | 2,595 bytes |
コンパイル時間 | 1,684 ms |
コンパイル使用メモリ | 172,264 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-27 02:07:36 |
合計ジャッジ時間 | 9,558 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using db = double;using ld = long double;#define fs first#define sc second#define pb push_back#define mp make_pair#define mt make_tuple#define eb emplace_back#define all(v) (v).begin(), (v).end()#define siz(v) (ll)(v).size()#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)#define repr(i, a, n) for (ll i = n - 1; (ll)a <= i; i--)#define lb lower_bound#define ub upper_boundtypedef pair<int, int> P;typedef pair<ll, ll> PL;const ll mod = 1000000007;const ll INF = 1000000099;const ll LINF = (ll)(1e18 + 99);vector<ll> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};template <typename T>T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }template <typename T>T mpow(T a, T n){T res = 1;for (; n; n >>= 1){if (n & 1)res = res * a;a = a * a;}return res;}//cin.tie(0);ios::sync_with_stdio(false);ll two[61] = {};ll solve(vector<ll> &v, ll r){if(r<0)return 0;ll n = siz(v), x = 60;vector<bool> ch(n, false);ll dp[65][2] = {};dp[61][0] = 1;ch[n - 1] = true;while (x >= 0){ll y = two[x];ll ced = 0;bool f01 = 0, f10 = 0, st = (v[0] & y);rep(i, 0, n + 1){if (0 < i && ch[i - 1]){if (ced == 1){if (st == 1)f10 = true;elsef01 = true;}if (i == n)break;st = (v[i] & y);ced = 0;}if (i > 0 && !ch[i - 1] && (y & v[i]) != (y & v[i - 1])){ced++;if (ced == 2){return 0;}ch[i - 1] = true;}}if (f10 && f01){return 0;}else if (f10){if(r & y)dp[x][0] = dp[x + 1][0];}else if (f01){if (r & y)dp[x][1] = dp[x + 1][0];elsedp[x][0] = dp[x + 1][0];}else{if (r & y){dp[x][1] = dp[x + 1][0];}dp[x][0] = dp[x + 1][0];dp[x][1]+=dp[x+1][1];//}dp[x][1] += dp[x + 1][1];x--;}return dp[0][0] + dp[0][1];}signed main(){two[0] = 1;rep(i, 1, 61) two[i] = two[i - 1] * 2;ll n, l, r;cin >> n >> l >> r;vector<ll> v(n);rep(i, 0, n) cin >> v[i];cout << solve(v, r) -solve(v, l - 1) << endl;//cout << solve(v, l - 1) << endl;return 0;}