結果

問題 No.911 ラッキーソート
コンテスト
ユーザー ferin
提出日時 2019-10-18 23:02:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,480 bytes
コンパイル時間 1,905 ms
コンパイル使用メモリ 178,584 KB
実行使用メモリ 22,456 KB
最終ジャッジ日時 2024-06-25 18:42:08
合計ジャッジ時間 9,314 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_ 
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

int main(void) {
    ll n, l, r;
    cin >> n >> l >> r;
    vector<ll> a(n);
    REP(i, n) cin >> a[i];

    // REP(i, n) cerr << bitset<15>(a[i]) << endl;

    auto solve = [&](ll x) -> ll {
        vector<ll> p;
        ll dp[61][2] = {};
        dp[0][0] = 1;
        REP(i, 60) {
            // if(i>=30) dump(i);
            // if(i>=30) cerr << "dp0=" << dp[i][0] << " dp1=" << dp[i][1] << endl; 
            // if(i>=30) dump(p);
            ll idx = 0;
            vector<vector<int>> v(p.size()+1);
            REP(j, n) {
                if(idx < p.size() && p[idx] == j) idx++; 
                v[idx].push_back(!!(a[j]&1LL<<(59-i)));
            }
            // if(i>=30) dump(v);
            
            ll sz = 0;
            vector<ll> np;
            bool ok0 = true, ok1 = true;
            for(auto vec: v) {
                ll turn = 0;
                if(vec[0]==0) {
                    REP(j, vec.size()) {
                        if(turn == 0) {
                            if(vec[j] == 0) turn = 0;
                            else turn = 1, np.push_back(sz+j);
                        } else if(turn == 1) {
                            if(vec[j] == 0) {
                                return 0;
                            } else {
                                turn = 1;
                            }
                        }
                    }
                    if(turn==1) ok1 = false;
                } else {
                    REP(j, vec.size()) {
                        if(turn == 0) {
                            if(vec[j] == 1) turn = 0;
                            else turn = 1, np.push_back(sz+j);
                        } else if(turn == 1) {
                            if(vec[j] == 1) {
                                return 0;
                            } else {
                                turn = 1;
                            }
                        }
                    }
                    if(turn==1) ok0 = false;
                }
                sz += vec.size();
            }
            // if(i>=30) cerr << ok0 << " " << ok1 << endl;

            if(ok0 && ok1) {
                ll nj = !!(x&1LL<<(59-i));
                dp[i+1][nj] += dp[i][0];
                dp[i+1][1] += dp[i][1];

                if(x&1LL<<(59-i)) dp[i+1][0] += dp[i][0];
                dp[i+1][1] += dp[i][1];
            } else if(ok0) {
                ll nj = !!(x&1LL<<(59-i));
                dp[i+1][nj] += dp[i][0];
                dp[i+1][1] += dp[i][1];
            } else if(ok1) {
                if(x&1LL<<(59-i)) dp[i+1][0] += dp[i][0];
                dp[i+1][1] += dp[i][1];
            }
            for(auto j: np) p.push_back(j);
            sort(ALL(p));
        }

        // dump(dp[60][0]);
        // dump(dp[60][1]);
        return dp[60][0]+dp[60][1];
    };

    // solve(r);
    cout << solve(r) - (l==0?0:solve(l-1)) << endl;

    return 0;
}
0