fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4.  
  5. const ll N = 30 + 1, M = 18, K = 10001, OO = 2e18l, L = 18, MOD = 1e9 + 7, sumD = 6638449, inv = 500000004;
  6.  
  7. ll l, r, x, dp[N][2][2];
  8.  
  9. ll count(ll i, bool f1, bool f2) {
  10.     if (i < 0) return 1;
  11.     ll &ret = dp[i][f1][f2], bit1 = ((l >> i) & 1), bit2 = ((r >> i) & 1), OR = ((x >> i) & 1);
  12.     if (~ret)
  13.         return ret;
  14.     ret = 0;
  15.     ll st = (f1 ? bit1 : 0), en = (f2 ? bit2 : 1);
  16.     if(OR == 0) {
  17.         if(st == 0) ret += (count(i - 1, f1 & (0 == bit1), f2 & (0 == bit2)));
  18.     }
  19.     else {
  20.         if(en == 1) ret += (count(i - 1, f1 & (1 == bit1), f2 & (1 == bit2)));
  21.         if(st == 0) ret += (count(i - 1, f1 & (0 == bit1), f2 & (0 == bit2)));
  22.     }
  23.     return ret;
  24. }
  25.  
  26. ll slv() {
  27.     memset(dp, -1, sizeof dp);
  28.     ll y = x, mx = count(30, 1, 1);
  29.     for(int i = 0; i < 30; i++) {
  30.         if(y >> i & 1) {
  31.             x = y;
  32.             x ^= 1 << i;
  33.             x |= (1 << i) - 1;
  34.             memset(dp, -1, sizeof dp);
  35.             mx = max(mx, count(30, 1, 1));
  36.         }
  37.     }
  38.     x = y;
  39.     return mx;
  40. }
  41.  
  42. ll bf() {
  43.     const int NN = 1 << (r - l + 1);
  44.     int mx = 0;
  45.     for(int mask = 0; mask < NN; mask++) {
  46.         int oo = 0;
  47.         for(int i = l; i <= r; i++) {
  48.             if(mask >> (i - l) & 1) {
  49.                 oo |= i;
  50.             }
  51.         }
  52.         if(oo <= x) {
  53.             mx = max(mx, __builtin_popcount(mask));
  54.         }
  55.     }
  56.     return mx;
  57. }
  58.  
  59. void solve() {
  60.     cin >> l >> r >> x;
  61.     cout << slv();
  62. //    for(l = 1; l < 16; l++) {
  63. //        for(r = l; r < 16; r++) {
  64. //            for(x = 1; x <= 16; x++) {
  65. //                if(bf() != slv()) {
  66. //                    cout << l << ' ' << r << ' ' << x << '\n';
  67. //                    cout << "right " << bf() << '\n';
  68. //                    cout << "wrong " << slv() << '\n';
  69. //                }
  70. //            }
  71. //        }
  72. //    }
  73. //    cout << count(30, 1, 1, 1);
  74. }
  75.  
  76. signed main() {
  77. //    l = 2, r = 5, x = 6;
  78. //    cout << slv() << '\n';
  79.     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  80.     ll t = 1;
  81.     cin >> t;
  82.     while (t--) { solve(); cout << "\n";}
  83. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/lyPGCi
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!