fork download
copy 
  1. //ngqmminh.cl2735
  2. #include <bits/stdc++.h>
  3. #define MOD 1000000007
  4. #define maxn 55
  5. #define Task "BITSWAP"
  6. #define reset(x, i) memset(x,i,sizeof(x))
  7. #define Random(lf, rt) (lf + rand() % (rt - (lf) + 1))
  8. #define PB push_back
  9. #define F first
  10. #define S second
  11. #define vi vector<int>
  12. #define pii pair<int, int>
  13. #define vii vector<pii>
  14. #define sz(x) int(x.size())
  15. #define all(x) x.begin(), x.end()
  16. using namespace std;
  17. typedef long long ll;
  18. typedef long double ld;
  19. int n, L = 0;
  20. ll a[maxn];
  21. int cnt[maxn];
  22. int dp[maxn][65];
  23. int tinh(int l, int r, int u, int v)
  24. {
  25.     int lf = max(l, u);
  26.     int rt = min(r, v);
  27.     if(lf > rt) return 0;
  28.     return rt - lf + 1;
  29. }
  30. pair<pii, int> trace[maxn][65];
  31. ll ans[maxn];
  32. int main()
  33. {
  34.     ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
  35.     if(fopen(Task".inp", "r"))
  36.     {
  37.         freopen(Task".inp", "r", stdin);
  38.         freopen(Task".out", "w", stdout);
  39.     }
  40.     cin >> n;
  41.     for (int i = 1; i <= n; i ++){
  42.         cin >> a[i];
  43.         for (int j = 60; j >= 0; j --)
  44.             if ((a[i] >> j) & 1ll){
  45.                     cnt[i] ++;
  46.                     L = max(L, j + 1);
  47.             }
  48.     }
  49.     dp[1][cnt[1]] = 1;
  50.     trace[1][cnt[1]] = {{cnt[1], 0}, 0};
  51.     for (int i = 1; i < n; i ++)
  52.         for (int numOne = 0; numOne <= L; numOne ++)
  53.             if(dp[i][numOne])
  54.                 for (int j = 1; j + cnt[i + 1] - 1 <= L; j ++)
  55.                 {
  56.                     int tmp = 0;
  57.                     tmp += tinh(1, numOne, 1, j - 1);
  58.                     tmp += tinh(1, numOne, j + cnt[i + 1], L);
  59.                     int cc = tmp;
  60.                     tmp += tinh(numOne + 1, L, j, j + cnt[i + 1] - 1);
  61.                     dp[i + 1][tmp] = 1;
  62.                     trace[i + 1][tmp] = {{tmp - cc, cc}, numOne};
  63.                 }
  64.     if(!dp[n][0])
  65.     {
  66.         cout << 0;
  67.         return 0;
  68.     }
  69.     vii v;
  70.     int x = 0;
  71.     for (int i = n; i >= 1; i --)
  72.     {
  73.         pii tmp = trace[i][x].F;
  74.         v.PB(tmp);
  75.         x = trace[i][x].S;
  76.     }
  77.     v.PB({0, 0});
  78.     reverse(all(v));
  79.     ll cur = 0;
  80.     for(int i = 1; i <= n; i ++)
  81.     {
  82.         vi pos[2];
  83.         for (int j = 0; j <= 60; j ++)
  84.         {
  85.             int tmp = ((cur >> j)&1ll);
  86.             pos[tmp].PB(j);
  87.         }
  88.         int zto = v[i].F;
  89.         int otz = v[i].S;
  90.         ll tmp = cur;
  91.         for (int i : pos[0])
  92.         {
  93.             if(zto == 0) break;
  94.             tmp += (1ll << i);
  95.             zto --;
  96.         }
  97.         for (int i : pos[1])
  98.         {
  99.             if(otz == 0) break;
  100.             tmp -= (1ll << i);
  101.             otz --;
  102.         }
  103.         cout << tmp << " ";
  104.         cur ^= tmp;
  105.     }
  106. }
Success #stdin #stdout 0.01s 5432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0DEnVK
language:
C++14 (clang 8.0)
created:
1 year 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!