結果
問題 | No.911 ラッキーソート |
ユーザー |
![]() |
提出日時 | 2019-10-21 00:39:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 257 ms / 2,000 ms |
コード長 | 3,641 bytes |
コンパイル時間 | 1,960 ms |
コンパイル使用メモリ | 174,744 KB |
実行使用メモリ | 11,144 KB |
最終ジャッジ日時 | 2024-07-02 17:37:05 |
合計ジャッジ時間 | 7,722 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h>#define all(vec) vec.begin(), vec.end()using namespace std;using ll = long long;using P = pair<int, int>;constexpr ll INF = (1LL << 30) - 1LL;constexpr ll LINF = (1LL << 60) - 1LL;constexpr ll MOD = 1e9 + 7;template <typename T> void chmin(T &a, T b) { a = min(a, b); }template <typename T> void chmax(T &a, T b) { a = max(a, b); }int n;vector<ll> a;ll solve(ll ub) {ll dp[64][2][2] = {};dp[62][0][1] = 1;vector<P> v;v.push_back(P(0, n - 1));for (int i = 61; i >= 0; i--) {int c1 = 0, c2 = 0, c3 = 0;vector<P> nv;for (auto &p : v) {int f0 = 0, f1 = 0, t = ((a[p.first] >> i) & 1LL);if (t == 0) {f0++;} else {f1++;}int tm = -1;for (int j = p.first + 1; j <= p.second; j++) {if ((a[j] >> i) & 1) {if (t == 1) {if (f0 > 0) {return 0;}} else if (f1 == 0) {nv.push_back(P(p.first, j - 1));tm = j - 1;}f1++;} else {if (t == 0) {if (f1 > 0) {return 0;}} else if (f0 == 0) {nv.push_back(P(p.first, j - 1));tm = j - 1;}f0++;}}if (tm == -1) {tm = p.first - 1;}nv.push_back(P(tm + 1, p.second));if (f0 == 0 || f1 == 0) {c3++;} else if (t == 0) {c1++;} else {c2++;}}if (c1 > 0) {if (c2 > 0) {return 0;}if ((ub >> i) & 1LL) {dp[i][0][0] += dp[i + 1][1][0] + dp[i + 1][0][1] +dp[i + 1][0][0] + dp[i + 1][1][1];} else {dp[i][0][0] += dp[i + 1][1][0] + dp[i + 1][0][0];dp[i][0][1] += dp[i + 1][0][1] + dp[i + 1][1][1];}} else if (c2 > 0) {if (c1 > 0) {return 0;}if ((ub >> i) & 1LL) {dp[i][1][0] += dp[i + 1][1][0] + dp[i + 1][0][0];dp[i][1][1] += dp[i + 1][0][1] + dp[i + 1][1][1];} else {dp[i][1][0] += dp[i + 1][1][0] + dp[i + 1][0][0];}} else {if ((ub >> i) & 1LL) {dp[i][0][0] += dp[i + 1][0][0] + dp[i + 1][0][1] +dp[i + 1][1][0] + dp[i + 1][1][1];dp[i][1][0] += dp[i + 1][0][0] + dp[i + 1][1][0];dp[i][1][1] += dp[i + 1][1][1] + dp[i + 1][0][1];} else {dp[i][1][0] += dp[i + 1][0][0] + dp[i + 1][1][0];dp[i][0][0] += dp[i + 1][0][0] + dp[i + 1][1][0];dp[i][0][1] += dp[i + 1][1][1] + dp[i + 1][0][1];}}swap(nv, v);}return dp[0][0][0] + dp[0][0][1] + dp[0][1][0] + dp[0][1][1];}int main() {cin.tie(0);ios::sync_with_stdio(false);cin >> n;ll l, r;cin >> l >> r;a.resize(n);for (int i = 0; i < n; i++) {cin >> a[i];}ll res = solve(r);if (l > 0) {res -= solve(l - 1);}cout << res << endl;}